N=900;
H=[-8883552,-8024557,-7378030,-7387931,-6790063,-6671637,-6140828,-5285016,-5279170,-5238301,-4772182,-4632835,-4203516,-4255711,-4107208,-3652870,-2762917,-1815193,-1459123,-1049700,-79059,-21462013,-20484857,-19498022,-18811571,-17880697,-17011217,-17070443,-17052041,-16407904,-15997418,-15268830,-14346902,-13861889,-13273840,-12326323,-11836296,-11554769,-10807504,-10617456,-10007972,-9141857,-28986056,-28111538,-27383032,-26695262,-25875917,-25756972,-25337802,-24882212,-24937294,-24528410,-24302587,-24398130,-23722440,-23287026,-23237403,-22712658,-22788608,-22504507,-22502394,-22305375,-21479220,-38940432,-38572351,-37631520,-36949951,-36466515,-36141992,-36023049,-36003465,-35105442,-34225891,-33511758,-33434378,-32762717,-32573638,-32519847,-31681523,-31692228,-31173805,-30802761,-30255705,-29483498,-45632067,-45494974,-44853640,-43962190,-43784980,-43675560,-42777722,-42664200,-42635439,-41846761,-41321462,-41010240,-40965877,-40989902,-40812404,-40568865,-40602230,-40282367,-39456573,-38958206,-38997648,-52946201,-52898941,-52447041,-51531112,-51599583,-51221535,-51237743,-50891666,-50081620,-50012652,-50116551,-49405458,-48541067,-48630941,-48075017,-47921652,-47316350,-47230349,-47122216,-47195187,-46365753,-63657629,-63051874,-62289204,-62285213,-61765376,-61835616,-61501883,-60728032,-60839043,-59925781,-58951805,-58516706,-57807785,-56964897,-56342898,-55855242,-55506426,-55162518,-54406085,-53916688,-53706706,-72913750,-72718289,-71991808,-71090725,-70909634,-70167068,-69913637,-69099362,-68589877,-67965002,-68027145,-67279448,-66599491,-66636817,-66525911,-65559432,-65148152,-65133832,-64602772,-64555415,-64652800,-85729258,-85358702,-84460688,-83814998,-82870421,-82051411,-81403471,-80607293,-80262776,-79505877,-79135277,-78285171,-77641832,-77396688,-76913742,-76653301,-76418828,-75751836,-74784508,-73840249,-73043841,-91405966,-91462418,-91438275,-91024617,-90502395,-90549039,-90457206,-90021084,-90114286,-89990976,-89688339,-89793530,-89812259,-89390561,-89163312,-88719479,-87888030,-86895066,-86858995,-86177396,-85801364,-101797278,-101487857,-100886506,-100266311,-99857048,-98883840,-98113294,-97592935,-97075373,-96185036,-95366665,-94773694,-94330567,-94035739,-93656568,-93052446,-92866728,-92496060,-91943008,-91865812,-91354935,-110894064,-110698367,-109727863,-109168221,-108878220,-108354806,-107357188,-107426529,-106478384,-106117993,-105848858,-105292889,-105071133,-104521386,-104059990,-103744043,-103477797,-103416648,-102785162,-101950117,-101873767,-120485998,-119683565,-118796322,-118476472,-117646579,-117336846,-117020191,-116670601,-116579498,-116688707,-116654596,-116681270,-116498626,-115602357,-114640767,-114154353,-114215044,-113413742,-113060565,-112478649,-111789884,-130840423,-129941870,-129669687,-129505090,-129530663,-128671846,-128005719,-127115659,-126889588,-126501568,-126416309,-125585476,-124924904,-124568184,-124490615,-123543256,-123495807,-123395034,-122548364,-121729926,-121234037,-141363145,-141242090,-140507877,-139849537,-139010261,-138579510,-138273884,-138037005,-137414454,-136965237,-136600938,-136303119,-135593525,-135406744,-134446968,-134514324,-133549017,-132549303,-132387337,-132158919,-131548338,-148008442,-147594198,-147680243,-147686217,-147623225,-147169495,-146325213,-145895865,-145522247,-144574218,-143996345,-144073581,-144167240,-144203095,-143303340,-142869791,-142808106,-142539340,-141786459,-141750314,-141606322,-157301443,-156308395,-156407786,-156301323,-155842461,-155846548,-155435971,-155382996,-154861860,-154132671,-153674098,-153175046,-152518058,-151900924,-151338070,-150635347,-149902388,-149441920,-148660324,-148203373,-147927964,-167117678,-166154741,-165899397,-165222934,-164616385,-164041452,-163360509,-162740563,-162584746,-161918818,-161973474,-161447697,-160491945,-159997855,-159870416,-159614601,-159541669,-159610878,-159094829,-158880786,-157900525,-176648740,-176025643,-175824644,-175769033,-175195574,-174645931,-174054194,-173100273,-172928066,-172705555,-172249896,-171690284,-170789280,-169975933,-170085488,-170092667,-169625933,-169566971,-168703741,-168579029,-167998938,-185056598,-184374808,-183737152,-183716290,-182963270,-182365028,-182300634,-181895550,-181851495,-181100125,-180313479,-180308962,-180245375,-179764523,-179303605,-178312687,-178105387,-178109967,-177148802,-177064929,-176979266,-194041806,-193799018,-193632438,-193427906,-193492814,-193177116,-192441983,-191684383,-191328003,-191137913,-190882095,-190240291,-189611702,-189262312,-188279369,-188001663,-187618026,-186985437,-186404361,-186400701,-185529696,-196921128,-196748800,-196310280,-196419474,-195702760,-194777992,-194887673,-194628928,-194012161,0,759225,701881,689038,1409922,2307379,2712904,3500191,3724590,3974203,4254231,4669320,4917378,5051809,5697668,6611855,6853284,7716439,8547512,8765328,9026013,9826281,10117341,10730312,11261187,11213143,11306892,11617827,11756561,11893497,12017885,11974672,12090361,13055695,13696453,14519866,15443012,15778718,15715283,16409524,17018210,16910307,17708173,18410573,18745180,19131454,20075221,19999619,20162852,20554127,21273811,21361688,21929652,22665321,23550499,24006854,24101746,24052383,24993019,25418366,26103565,26381737,26932390,27445831,28200176,28498733,29445044,30113794,31105220,31146258,31790219,32361927,32493687,33032342,33856714,34659702,34837415,34739951,34842068,35647120,35625718,36439389,37101751,37349435,37544015,38062992,38559935,39132941,39687990,39869868,39780601,40425089,40417010,40981009,41938799,42696680,43592099,44590944,44727418,45592253,45964241,46791065,47725436,48314312,48282692,48195630,48846159,49128967,50060661,50640567,50730929,51588894,51587879,52187474,52513887,52419726,52613197,52600707,53140496,53944871,54471891,55404477,55542259,55476440,56243111,56242388,56499804,56998565,57157796,57360799,57541499,58282601,58631808,58733084,59355795,60225662,60407902,60720147,60666942,61186341,62099473,62854935,63709396,64614026,64532466,64491618,65293235,65230276,66065416,66040467,66379545,66977169,67802273,68405643,68504953,68415557,68885534,69126637,69149274,69564539,70101240,70872790,70830690,71216490,71554904,71768787,72401648,73360809,73564978,73829033,74340677,75081493,75610368,75891338,76005319,76466216,76932459,77810651,78676124,79511215,79886018,79855743,80227949,80118456,80183431,81092134,81689432,82582873,82732569,83417025,83542711,84064657,85056393,85080949,85963414,86466105,87160404,87311291,87487763,87573504,87857703,88625814,89530237,89895831,90790044,91344493,91969396,91954043,92876771,92894227,93171720,93814929,93899434,94262438,94702051,94612119,95505154,96476327,97234736,97191902,97678870,97595214,98006327,98906177,98815706,99309493,99622997,100020617,100885578,101849876,101995517,102736986,103243511,104175075,104719703,105596480,106451749,106712901,107331711,107434555,107878737,108648625,108840661,108838194,109392552,109302248,109614431,110128535,110070895,110681632,110630562,110699254,111535042,112276895,112271163,112471660,112384521,112806675,113269907,114072901,114507749,114638749,114843538,115068519,115525069,115836255,116750562,117722472,118710208,119630245,120454264,121097887,121447752,122186009,122976552,122911150,122805236,123079453,123198562,123326330,123604400,123933776,124181688,124585511,124696432,125026031,125030931,125769427,126411996,127080986,127778920,128088873,128201687,129046896,129274947,129690618,130508181,130576733,130635404,131475067,132382878,132986795,133824061,134465501,135254949,136197741,136112161,136168363,136189276,136842080,137398018,137995763,138276145,138166831,139037980,139391372,140267052,140631494,140716287,140682371,141275815,141502613,141712423,142057546,142194189,142461574,142894334,143436915,143740395,143716800,144181248,144230314,144691334,145166690,145921695,146664434,147424012,147483612,147746928,148670730,148710797,149300743,149211328,149492887,149777208,150035741,150608258,150511580,150516493,151026076,151595116,152274354,152647257,152804019,153650435,153986677,154390758,154797727,155725379,156487980,157078954,157314658,157229247,157345179,158146893,158594381,159146174,159204981,159277963,160099962,160366486,160442143,161025716,161653323,162163237,163100963,163102226,163624963,164119995,164012433,164863972,165817626,165823243,166730033,167646189,167912728,167896041,168075162,168829797,169724192,169897933,169844309,169975053,170966104,171063145,171282316,171478657,172464135,172354037,172353000,172735711,173206113,173120121,173123722,173472677,174160744,174663384,174912391,175469322,175851727,176021651,176839330,177094846,177423578,177985298,177886613,178015761,178847503,178862464,179599656,180061972,179969072,180775232,181671135,182453831,183434736,183987903,183932094,183914606,184304072,185054152,185466970,185783706,186161925,186672574,186702367,186888756,186806294,186847870,187735185,188537635,188941642,188992640,189670840,190302623,190250467,191168984,192138786,193102199,193041891];
X0=364213441;
M=7000;
S=[493,748,571,251,853,30,352,490,246,574,753,814,721,411,432,495,888,28,453,158,37,448,202,298,839,348,653,595,407,666,141,637,16,801,662,849,805,73,893,298,33,307,461,600,645,321,786,47,215,157,220,156,186,515,388,318,150,761,132,673,143,217,330,305,762,274,82,27,794,708,642,830,267,683,424,638,641,168,271,891,217,50,3,222,786,329,525,225,856,286,84,307,640,820,284,449,696,879,201,365,618,203,508,457,425,448,643,115,442,803,108,643,547,23,663,439,370,652,406,801,546,83,871,136,812,262,701,729,543,107,776,78,86,106,749,277,184,1,175,421,342,118,74,727,350,896,542,561,91,567,768,329,245,791,58,834,432,113,626,9,433,416,304,104,891,120,146,513,766,470,226,535,646,9,287,146,576,461,549,475,655,350,181,621,875,620,294,460,488,500,264,96,167,817,67,450,719,655,383,5,468,667,533,577,55,115,600,362,798,189,781,21,203,417,606,485,157,609,213,310,29,603,93,580,853,726,374,276,855,446,109,429,95,460,617,339,175,686,718,498,597,514,876,575,108,667,347,29,104,138,872,144,477,386,10,336,168,351,26,362,232,321,638,640,685,748,492,109,883,837,655,854,819,411,671,125,628,466,629,868,274,403,832,757,41,496,216,856,322,67,317,731,440,604,59,248,735,721,407,566,224,656,684,694,409,352,115,410,132,545,330,128,740,156,459,223,410,863,253,324,852,348,424,505,160,151,77,596,334,386,683,36,852,683,54,778,100,845,750,240,893,128,675,632,287,820,722,889,270,754,370,179,107,661,708,659,241,733,622,452,224,427,682,170,384,606,99,861,694,114,649,266,313,631,381,184,233,745,818,519,190,369,208,319,209,594,591,233,365,440,171,88,238,168,893,660,137,204,812,649,812,362,745,100,681,410,582,44,187,846,221,621,539,128,333,787,155,663,858,15,885,223,781,456,176,492,253,694,165,815,230,769,763,647,592,774,69,748,203,623,190,51,252,415,859,755,658,115,670,824,402,133,550,134,658,279,143,89,872,815,265,666,419,801,393,128,235,23,782,731,417,87,96,700,380,552,123,85,740,295,712,116,601,290,50,165,695,47,821,438,803,1,266,577,384,221,823,693,434,385,618,270,898,863,298,513,819,526,408,860,437,399,282,837,392,516,530,227,533,487,739,103,346,391,758,60,58,864,410,350,70,651,870,353,487,583,689,117,558,564,708,555,482,718,597,358,531,678,103,358,206,279,146,264,582,709,730,590,295,416,256,566,149,281,107,664,397,107,519,530,77,702,860,254,728,894,595,15,847,268,79,521,799,435,368,213,165,363,618,333,404,352,638,347,564,331,231,6,154,427,321,631,173,276,77,857,685,34,473,524,70,710,851,16,869,150,522,65,432,365,511,540,657,148,588,424,312,601,867,785,23,694,36,752,484,621,629,172,302,94,840,260,633,39,272,899,618,398,373,38,748,654,895,327,295,704,11,381,223,294,532,760,13,670,690,169,87,43,341,186,635,274,142,89,209,493,688,14,543,626,567,595,891,828,339,314,452,204,653,6,278,296,620,475,742,130,416,513,807,553,446,653,269,833,876,62,868,403,512,156,629,206,797,276,878,810,540,509,857,847,495,191,138,526,156,698,255,826,543,22,714,463,882,188,618,297,283,591,323,701,269,811,506,54,308,217,102,284,384,75,595,599,710,103,649,808,205,469,97,38,685,539,93,709,478,339,523,149,545,644,435,831,61,730,655,886,482,489,761,386,180,742,108,483,28,44,492,350,721,783,898,825,327,332,41,31,503,266,785,285,215,773,354,817,797,725,493,21,144,882,400,136,845,561,561,795,182,449,360,739,213,758,587,173,421,121,256,824,19,520,382,705,882,249,553,110,829,220,866,405,639,59,200,25,89,476,451,59,393,514,615,501,602,9,553,257,376,890,507,206,767,131,15,81,560,134,721,412,678,794,243,673,149,736,247,631,289,119,484,570,503,763,570,631,114,84,638,797,414,386,119,796,352,542,845,316,282,539,328,354,790,597,209,833,579,93,402,729,458,249,817,874,77,539,278,81,470,335,459,545,792,103,86,342,224,405,598,356,217,180,583,240,38,424,482,825,146,314,762,291,646,844,283,522,188,440,481,755,387,754,77,697,783,208,1,300,164,108,431,192,839,857,183,866,15,327,775,641,528,270,529,561,202,643,468,598,294,813,180,845,607,264,330,684,633,1,761,10,856,879,465,800,877,142,222,19,139,726,440,348,406,443,448,174,671,702,421,54,772,478,472,402,27,687,799,184,183,706,820,71,177,361,314,92,863,470,165,865,195,509,798,892,777,536,880,608,259,701,187,322,243,223,567,704,268,822,16,780,90,242,75,801,1,484,355,360,798,419,825,555,656,167,843,352,703,313,735,490,287,280,44,389,249,868,274,378,556,181,446,372,868,803,867,651,569,123,109,579,784,556,236,189,584,418,156,500,553,518,846,188,688,6,149,701,191,796,678,324,196,564,243,264,562,372,58,277,786,822,62,243,718,305,243,563,120,701,642,532,756,579,674,174,208,745,23,533,558,237,473,322,401,442,424,36,857,641,461,667,58,609,199,295,173,42,531,365,489,788,491,131,550,167,617,420,108,612,32,181,396,394,868,7,113,25,138,115,231,486,593,28,718,711,161,83,3,282,634,58,429,419,36,255,740,252,380,305,21,135,185,161,814,535,12,9,189,544,855,83,845,395,348,642,707,234,358,171,821,351,417,404,241,561,538,831,854,441,724,279,269,690,203,421,645,240,759,379,717,863,528,307,60,891,415,168,11,749,119,106,224,348,297,678,562,824,43,767,621,810,483,601,145,869,468,120,15,504,418,661,762,722,202,831,250,464,151,834,495,900,649,62,474,445,560,868,882,271,608,595,311,647,230,843,890,635,405,188,641,77,145,719,898,557,631,351,788,241,662,524,576,399,898,662,664,670,895,890,698,738,50,771,397,183,397,121,274,498,471,28,852,98,637,105,814,147,368,694,503,562,761,198,876,802,71,646,811,139,138,707,891,277,479,254,408,732,177,894,414,413,356,664,578,155,880,802,815,298,330,342,881,39,272,51,448,308,601,74,573,75,834,425,579,844,796,522,586,125,280,224,190,160,481,688,308,832,27,504,811,889,395,298,583,863,876,617,885,859,578,818,615,96,61,559,843,262,322,726,112,802,431,802,775,267,698,623,838,801,527,58,255,660,744,298,582,520,315,591,377,514,319,753,806,97,740,393,80,89,75,282,619,271,403,768,51,493,264,351,37,229,454,708,116,555,882,818,620,765,758,165,629,897,680,273,420,774,320,163,584,508,888,622,97,596,630,130,563,276,69,855,131,218,141,430,436,677,267,2,466,558,606,407,574,744,762,489,78,679,879,629,224,531,602,321,495,340,433,740,652,755,70,355,229,671,489,32,736,252,688,813,21,879,181,400,422,286,127,525,481,535,450,206,269,254,47,473,442,513,125,693,760,326,208,195,656,520,56,333,133,851,890,613,387,844,488,378,226,821,688,93,79,572,206,884,785,61,88,369,792,718,500,619,672,849,165,735,266,781,755,479,305,630,47,609,253,76,368,228,423,556,114,740,593,553,601,466,701,739,830,81,526,599,599,841,745,148,686,654,256,178,315,33,613,157,216,501,895,257,87,738,199,339,423,868,148,450,596,884,801,638,27,629,453,652,807,407,253,126,180,14,619,658,98,347,866,612,26,317,818,422,6,708,891,186,240,896,814,695,512,790,318,613,344,221,235,712,842,733,305,429,605,710,505,343,9,653,574,194,619,28,608,311,702,482,648,117,190,324,368,36,131,424,718,820,306,860,53,781,653,42,530,32,482,682,859,56,145,654,166,749,492,400,738,324,445,299,256,731,331,20,239,44,722,849,578,579,899,544,208,70,617,636,502,11,496,514,318,705,572,596,743,108,154,240,89,820,500,229,832,406,620,384,529,145,798,711,483,369,24,472,442,843,268,110,862,766,321,669,576,166,271,330,415,859,355,292,275,1,824,579,36,165,666,323,295,750,577,457,791,692,578,276,592,424,167,292,695,140,674,325,830,622,415,72,67,378,396,424,65,678,379,261,105,896,543,555,105,511,532,7,27,791,827,84,299,897,323,882,863,3,832,613,181,635,526,446,504,432,661,664,92,607,106,819,33,67,500,103,404,872,568,821,304,846,80,83,357,545,674,860,255,854,773,777,803,376,765,672,492,199,183,415,194,520,26,192,553,562,806,511,590,468,507,94,152,33,393,351,15,298,661,705,28,497,474,373,57,521,389,785,536,310,304,887,268,525,257,442,78,108,351,215,724,9,630,656,772,292,867,67,62,703,897,803,232,280,680,21,716,54,508,435,501,177,213,775,795,609,584,24,518,811,552,342,475,166,74,106,861,738,136,147,136,532,24,813,352,123,765,604,870,899,859,297,357,492,759,543,717,898,648,386,802,714,430,282,609,731,445,304,661,685,569,59,22,105,735,279,101,805,86,296,52,407,167,895,341,187,260,155,287,299,11,244,743,133,131,70,255,680,256,438,761,324,743,267,476,165,159,453,185,324,616,644,103,588,502,393,269,749,669,102,730,148,158,298,211,620,496,194,714,685,716,848,854,363,288,322,411,22,266,22,813,891,741,468,185,753,485,842,82,396,499,374,620,629,350,747,867,718,574,182,256,609,519,729,886,318,377,358,381,735,637,744,714,130,214,640,699,254,805,80,774,691,72,842,2,754,757,581,256,69,739,78,758,310,326,399,526,604,679,602,687,616,784,582,362,749,888,603,686,595,28,106,134,114,125,874,413,42,88,355,508,280,832,565,833,95,481,345,107,31,832,722,602,609,552,672,818,675,789,479,564,603,707,508,375,245,559,166,751,279,527,781,288,215,586,601,227,820,385,131,83,522,185,194,432,766,627,570,867,690,834,163,70,640,666,342,131,336,308,386,161,604,599,75,889,206,583,493,197,265,524,821,427,257,563,561,666,38,434,764,711,721,227,283,52,449,422,852,243,890,213,817,288,121,74,297,597,393,676,233,588,310,735,818,816,480,416,657,449,699,498,517,207,412,769,115,827,774,313,321,808,713,719,597,550,722,649,398,793,43,629,309,26,26,327,768,708,315,797,209,199,512,129,875,547,59,170,263,173,139,384,151,528,676,112,369,348,846,53,252,894,762,355,573,680,159,102,470,636,741,139,493,29,601,556,689,436,10,511,802,91,160,252,313,64,171,149,713,127,615,460,450,6,141,264,892,163,428,621,100,393,816,376,345,528,174,700,835,232,20,725,362,870,792,779,311,173,662,35,777,149,20,279,56,602,544,269,500,817,685,277,14,769,399,517,337,678,338,155,429,548,871,646,502,212,525,638,625,321,788,828,417,771,117,727,58,211,707,511,848,519,386,640,188,605,214,451,212,316,91,662,703,841,498,771,622,782,286,154,266,285,723,141,460,841,550,518,727,683,873,104,640,806,14,751,785,845,893,56,828,419,60,526,888,141,341,597,542,125,143,425,800,202,110,99,872,516,243,361,353,587,564,781,820,508,591,199,339,450,3,753,104,437,37,541,426,249,108,302,366,259,664,396,182,682,41,272,264,426,855,517,759,80,879,183,375,262,344,190,153,666,38,275,436,99,30,236,296,2,3,195,529,869,260,164,824,138,532,453,324,560,832,408,609,8,462,876,591,761,677,897,183,454,473,504,216,534,615,720,102,606,457,601,65,8,389,15,470,55,299,587,236,527,829,19,279,424,33,757,287,411,290,77,209,535,660,517,780,96,891,447,616,654,640,354,317,138,642,98,440,815,25,412,19,561,298,739,729,641,132,455,251,473,731,768,510,555,399,603,815,850,748,850,53,811,307,347,97,176,571,38,665,707,320,549,215,367,39,766,562,85,382,248,147,123,859,631,224,619,894,44,203,365,193,514,311,875,542,117,121,683,48,105,219,484,687,650,187,354,759,93,740,857,305,757,783,458,156,399,686,712,408,193,323,267,230,801,17,899,889,14,836,181,529,728,621,344,810,704,519,688,568,49,738,153,660,131,338,512,505,770,524,744,427,398,791,625,431,504,815,352,475,587,136,619,669,780,431,516,481,441,163,882,29,640,180,322,207,160,214,478,38,793,410,228,574,440,251,376,72,728,213,872,114,501,248,126,522,59,573,301,599,830,255,261,18,103,402,114,350,773,486,489,511,729,828,229,1,709,862,250,340,735,739,888,713,130,588,92,307,102,131,485,466,424,94,615,235,727,111,306,576,243,562,351,595,316,717,641,344,386,406,56,685,894,832,385,876,751,376,386,292,162,816,193,37,765,330,837,352,642,393,455,483,864,14,625,440,131,27,889,299,880,742,242,242,34,622,157,879,817,848,685,733,557,54,685,860,422,770,28,644,197,163,87,342,349,649,584,709,499,197,370,741,1,474,789,435,233,304,37,822,118,879,551,474,172,156,834,67,200,354,718,469,5,285,627,301,343,877,866,214,778,147,690,516,130,570,603,120,472,798,838,396,603,223,413,654,132,470,874,186,613,510,428,138,72,279,292,892,272,385,84,599,761,321,522,751,60,550,769,388,180,312,654,15,245,327,604,475,527,200,526,592,446,81,651,179,707,565,752,623,281,213,359,804,20,859,707,146,473,773,860,253,91,497,370,270,230,771,362,848,794,681,3,495,400,529,637,780,606,618,704,889,475,805,581,96,732,80,507,481,354,373,866,326,670,115,631,201,831,211,596,357,385,683,891,854,133,393,279,632,810,168,665,776,868,361,751,809,343,734,771,183,404,417,532,415,353,421,843,72,189,794,250,58,629,853,875,53,466,453,358,505,689,858,213,343,649,656,870,698,670,4,16,766,681,633,595,520,825,735,603,526,222,802,853,274,4,431,840,720,596,445,844,538,296,624,41,866,622,780,552,731,850,458,520,421,586,769,145,309,180,777,631,177,495,670,79,423,607,385,268,558,461,289,298,119,636,682,26,581,744,848,242,376,525,856,736,308,756,780,47,261,579,251,356,464,476,346,201,388,63,671,620,829,438,40,301,220,283,515,358,727,629,316,781,540,112,517,421,699,725,692,450,230,239,500,520,323,766,82,652,397,658,844,549,348,272,72,171,121,602,265,278,326,758,524,795,317,776,123,509,310,538,428,880,687,574,730,584,654,187,858,250,66,369,338,825,359,313,344,125,365,450,367,899,665,548,167,329,754,243,477,425,800,732,800,222,828,273,672,565,197,748,569,272,627,41,156,93,126,46,68,847,334,233,281,687,272,57,463,816,235,794,679,17,83,821,724,169,241,117,62,557,351,290,621,291,419,784,334,346,393,372,648,782,751,216,479,535,391,762,351,814,324,186,817,14,26,710,112,39,517,112,168,561,86,3,697,577,832,239,364,526,155,597,567,660,900,828,513,244,250,280,427,192,401,353,707,46,797,768,119,357,470,791,725,46,309,612,461,491,329,399,229,650,94,26,707,502,377,651,618,808,516,101,343,87,725,636,488,806,728,881,543,496,455,827,87,870,664,298,101,882,394,842,331,335,269,152,343,581,190,298,816,540,471,798,595,41,602,152,162,711,802,898,231,234,220,218,757,746,239,495,528,796,23,77,41,539,360,441,707,375,530,154,870,229,482,516,342,843,99,847,216,659,149,648,47,892,421,85,771,703,381,888,884,550,307,777,355,191,103,482,599,613,515,741,8,781,577,861,838,625,108,818,538,471,900,93,815,215,682,201,225,131,900,622,552,877,216,432,549,636,833,731,679,720,712,900,294,757,420,106,622,416,365,650,596,712,723,126,618,721,162,108,515,307,291,595,80,255,109,679,647,308,404,305,654,806,21,892,68,845,671,724,358,266,70,877,597,544,238,3,726,819,663,159,604,136,214,336,848,5,134,799,648,292,851,410,30,488,670,183,37,854,609,737,422,852,390,108,515,804,369,101,770,474,316,895,90,396,609,118,252,616,735,462,426,797,478,843,194,91,586,154,771,22,116,42,253,163,339,56,257,629,523,410,594,156,465,454,728,40,208,243,687,358,516,25,72,645,649,61,658,197,251,710,109,746,359,64,457,329,792,179,695,221,694,835,362,558,726,329,490,229,758,144,119,8,768,145,866,593,488,446,110,583,812,145,639,743,494,601,481,435,61,374,613,381,101,633,742,597,294,621,24,1,609,218,311,659,681,172,864,521,862,847,186,642,13,680,81,163,729,534,825,18,210,386,895,586,476,118,697,627,683,432,738,581,92,391,475,197,770,651,33,866,425,301,829,604,282,576,258,71,179,232,665,124,38,137,20,190,619,671,5,565,756,335,847,538,843,804,799,735,395,87,43,666,900,330,629,870,239,43,876,312,290,69,781,650,843,132,418,634,297,589,89,435,425,119,517,670,474,94,571,754,144,182,753,558,283,687,825,417,643,242,782,620,781,466,692,653,516,664,236,747,8,734,861,326,678,386,799,650,688,43,666,288,356,501,871,807,550,109,489,731,668,753,560,884,428,320,476,71,501,643,802,731,739,611,241,244,667,1,529,275,363,136,742,194,873,844,105,135,453,314,41,221,345,461,202,213,691,881,264,589,726,310,300,707,802,553,781,558,147,300,67,175,666,478,70,253,354,152,443,247,819,699,688,856,286,324,736,301,170,210,240,112,39,537,81,712,261,390,236,317,212,332,492,243,549,579,698,159,839,583,684,504,506,873,324,666,187,499,541,597,588,527,536,482,491,685,227,236,852,395,544,575,301,463,726,167,168,396,226,593,556,346,658,216,641,214,792,448,55,343,235,274,171,669,696,320,504,468,753,172,146,245,572,861,650,54,356,112,303,777,617,395,1,666,692,396,804,707,616,735,128,62,205,446,738,574,291,159,33,67,639,829,505,106,272,164,55,218,710,752,541,131,285,666,373,309,46,829,723,585,740,357,273,269,99,418,189,627,583,477,642,631,793,269,844,231,496,186,864,113,608,188,256,160,285,40,362,612,76,77,721,574,760,579,54,249,301,511,500,437,747,307,39,582,743,105,795,157,167,856,448,588,226,65,643,833,669,634,815,284,489,109,364,307,127,258,379,68,786,139,894,70,383,890,403,769,740,885,430,242,631,139,625,516,183,313,766,235,493,9,20,47,431,610,875,729,439,380,332,411,620,631,453,323,783,256,284,705,10,594,688,23,551,237,390,123,9,5,785,356,117,707,333,26,525,78,678,38,431,798,880,167,2,548,636,229,558,462,841,712,124,810,55,549,835,627,643,38,191,654,52,665,876,877,673,674,479,74,125,43,295,864,497,542,532,60,859,498,670,189,198,167,454,66,302,394,743,242,588,850,241,474,698,323,640,40,106,277,313,899,28,65,519,11,214,173,446,900,682,419,542,239,775,691,736,687,781,399,211,688,696,649,483,142,217,484,780,246,563,272,583,435,46,834,158,29,483,853,704,701,581,209,890,805,212,114,378,715,480,41,514,150,289,600,636,155,688,53,376,780,380,228,164,651,581,491,570,815,544,472,369,237,227,830,534,52,116,893,295,19,639,14,598,105,578,336,778,319,267,755,184,847,549,311,62,576,332,157,294,778,128,771,371,533,814,59,490,582,253,685,157,120,437,147,558,523,351,215,624,451,362,700,279,369,386,582,608,872,311,202,430,284,581,363,201,845,505,801,309,520,386,652,767,160,268,64,358,61,812,254,870,72,672,413,227,803,310,118,350,728,118,463,490,198,774,494,787,598,340,466,97,510,507,795,797,132,331,526,514,688,809,182,468,860,547,271,199,858,7,845,216,357,196,836,666,453,139,449,825,342,327,115,589,449,336,119,187,141,778,411,29,582,401,253,878,400,2,44,759,392,580,48,502,189,627,54,817,355,76,245,270,118,273,157,413,439,788,246,760,553,889,404,741,468,578,372,203,853,557,277,331,178,245,124,623,369,18,859,281,125,565,608,840,315,836,286,617,273,365,85,790,109,700,730,25,271,875,852,305,837,308,279,619,605,42,535,177,494,269,508,613,408,165,603,442,379,39,239,204,632,42,205,248,394,586,107,513,889,324,687,275,677,503,152,538,503,47,698,415,178,136,418,377,550,722,3,336,135,750,281,540,570,179,292,506,714,69,760,825,643,697,202,69,530,305,169,58,825,499,622,77,314,119,455,861,244,599,510,582,216,781,250,320,720,452,763,544,178,484,306,557,417,325,298,307,394,220,691,14,80,524,141,63,342,293,280,744,443,68,377,204,740,704,771,384,171,345,39,866,475,591,387,584,588,118,649,684,698,807,716,722,446,305,416,836,351,480,218,44,185,449,709,613,268,350,689,288,417,845,538,755,171,458,688,84,570,311,784,614,527,14,885,870,240,602,31,134,391,651,3,656,599,30,452,791,329,481,118,596,619,870,601,757,487,732,730,300,684,180,59,308,331,609,291,345,391,463,291,176,479,30,328,48,722,738,455,501,353,380,367,751,770,123,36,755,264,219,607,828,723,545,595,830,35,863,364,101,509,515,214,438,452,553,82,736,380,515,170,475,349,651,817,231,432,44,556,549,872,594,136,716,789,330,818,312,119,442,677,249,659,28,833,692,308,623,839,360,386,820,478,673,138,618,78,543,582,749,883,723,520,285,830,635,771,438,389,894,756,853,234,781,821,781,777,266,188,242,544,831,845,245,85,426,526,669,431,739,785,801,382,256,205,104,791,719,826,615,9,547,864,476,76,633,868,574,52,695,117,413,730,643,795,406,432,480,870,355,68,755,291,362,162,546,825,759,544,251,332,12,888,17,92,667,437,765,446,831,311,429,33,444,763,299,725,46,448,294,751,186,438,146,329,111,125,292,485,205,834,35,758,369,179,735,557,594,670,712,500,372,375,495,673,391,112,735,156,659,619,408,543,389,887,346,368,372,212,794,446,156,15,139,105,34,139,413,597,888,148,300,551,428,722,73,34,366,158,683,30,540,570,18,343,376,628,402,398,629,160,656,442,811,796,747,11,142,522,719,657,431,765,380,65,573,297,727,282,516,263,398,408,537,354,444,572,43,194,374,340,586,711,838,10,110,410,514,777,739,373,201,198,882,146,896,851,814,361,848,510,327,216,850,698,58,773,173,824,133,519,894,311,702,678,875,778,717,147,734,208,120,1,294,74,633,676,432,374,183,392,378,195,150,386,246,865,131,388,659,508,316,356,570,717,415,218,9,831,647,156,734,350,101,252,736,110,488,537,247,312,696,611,780,811,489,307,510,635,363,676,553,193,555,122,537,643,124,29,155,771,654,430,310,84,622,619,138,483,342,542,755,526,676,531,58,103,44,700,94,481,756,375,835,801,158,507,781,414,869,120,237,223,685,7,498,747,671,807,804,343,773,752,231,465,789,570,36,652,667,146,450,668,593,126,517,45,597,552,461,236,482,284,167,44,792,32,46,65,839,306,430,163,784,233,39,243,526,833,330,184,809,611,641,730,582,190,439,469,664,310,801,110,407,159,56,792,127,425,857,575,316,421,727,468,139,22,171,557,387,497,151,700,692,444,405,12,651,453,696,526,350,895,289,300,31,846,634,152,114,87,705,362,605,225,885,260,342,892,179,232,868,788,657,777,507,757,777,115,503,444,790,546,677,240,393,71,184,278,160,817,36,876,797,20,586,756,611,56,125,481,82,442,817,699,107,369,62,499,101,677,264,68,424,58,152,730,456,689,577,845,898,49,483,393,773,74,163,591,33,197,115,790,590,220,417,39,317,213,289,20,189,627,569,467,682,471,583,355,744,399,102,156,576,749,610,175,117,473,420,203,231,821,630,500,162,791,122,38,879,682,799,509,705,758,134,594,900,847,206,328,468,118,479,280,214,422,1,656,812,471,744,770,777,77,761,713,546,893,483,165,836,598,218,855,88,336,715,458,465,819,880,22,92,144,127,483,539,566,264,405,772,497,561,797,394,726,488,694,354,607,460,45,606,510,33,508,260,314,828,897,383,644,239,415,384,274,828,102,661,642,610,743,660,875,526,77,580,278,775,24,818,650,369,628,288,342,128,281,216,101,164,260,113,40,58,20,155,781,129,718,299,739,177,452,852,314,627,880,258,358,362,21,721,216,897,491,294,223,619,691,148,495,37,732,143,360,465,754,315,859,482,181,693,355,352,321,456,740,772,891,704,39,760,154,93,686,666,422,188,459,298,528,396,869,446,83,509,645,176,839,219,789,19,824,19,443,123,27,364,130,40,362,186,527,819,432,137,621,463,278,310,203,512,469,839,788,499,18,815,781,783,644,459,336,216,271,564,832,294,660,51,869,793,886,795,399,570,573,505,191,792,725,747,416,867,163,323,102,712,625,872,85,485,102,459,738,724,323,494,364,269,281,155,255,22,285,757,379,889,2,357,125,773,76,653,608,394,492,11,436,412,61,374,358,340,283,147,76,49,662,352,300,791,543,563,509,3,640,639,372,840,63,496,851,38,780,403,788,369,617,687,271,701,604,184,54,731,228,818,471,846,269,390,701,350,500,855,800,96,344,381,280,790,725,68,786,98,543,897,381,100,479,571,881,782,883,854,510,846,793,2,821,295,61,372,501,605,145,19,2,257,407,479,88,417,794,296,192,823,862,283,5,426,608,859,555,779,35,828,659,529,607,490,211,44,352,666,345,728,167,830,664,205,414,445,389,192,571,900,14,580,506,621,149,205,325,74,314,396,346,665,771,275,280,302,818,568,127,447,226,287,244,286,395,118,842,602,229,867,381,44,645,265,285,654,642,160,739,506,412,101,325,839,779,114,573,126,252,337,79,489,46,290,17,814,41,151,521,208,869,326,602,420,451,730,812,208,118,151,528,810,122,533,469,429,280,113,675,77,62,154,310,275,698,804,159,354,39,708,352,694,246,257,59,175,285,323,576,394,262,782,525,58,592,454,392,767,784,100,348,409,729,247,517,897,530,7,468,214,170,493,764,28,490,11,657,639,476,543,195,12,615,541,111,86,187,815,139,889,780,151,737,169,331,232,157,107,723,254,509,10,696,757,95,618,274,578,386,639,462,4,738,522,159,747,76,893,713,8,35,27,269,818,523,333,877,309,512,477,855,665,675,485,238,662,118,131,807,753,895,343,660,445,178,359,487,710,145,209,147,285,94,40,81,736,28,233,584,521,879,266,447,620,204,793,605,583,346,457,459,568,745,379,323,354,809,505,368,333,439,681,662,557,413,706,493,615,521,433,710,458,687,272,188,614,861,129,607,292,193,135,175,259,774,790,417,27,712,495,664,396,844,501,152,2,873,360,809,638,403,576,208,367,670,282,692,773,351,573,121,69,400,633,212,265,423,230,763,783,692,449,152,539,189,365,146,875,700,246,242,665,476,112,230,324,461,28,672,176,804,585,32,754,288,519,224,324,425,782,858,168,535,651,793,805,658,449,377,116,623,168,366,48,637,816,305,889,693,146,253,863,261,412,294,134,371,761,240,119,562,250,416,473,610,189,93,768,16,396,683,225,379,645,190,267,255,4,747,217,372,591,305,358,770,412,148,563,194,338,217,334,467,514,766,454,806,34,341,715,341,600,593,74,342,191,451,121,424,444,185,494,331,81,289,349,188,864,39,796,642,212,257,853,413,802,737,191,761,780,142,786,78,796,852,354,873,517,195,128,469,399,148,855,871,635,574,99,561,720,737,889,497,486,49,420,326,321,187,340,40,846,622,37,364,296,550,375,241,611,683,663,551,543,478,356,606,137,150,774,298,364,467,666,880,156,534,38,383,637,541,592,880,380,810,836,69,112,384,520,340,305,460,818,448,535,396,37,193,3,514,153,736,408,217,38,140,534,454,661,585,769,360,497,519,510,42,230,682,691,131,565,691,563,560,609,177,391,623,718,393,721,811,868,485,195,896,519,83,839,282,540,546,325,174,866,346,263,591,185,776,267,277,778,615,308,84,19,459,215,429,6,864,702,147,547,778,7,170,640,650,865,551,507,651,325,892,571,870,237,587,212,125,143,771,739,858,774,113,106,460,315,235,811,43,208,419,677,436,875,200,253,101,899,771,858,201,20,243,748,289,99,579,731,434,807,478,231,393,752,193,513,225,174,42,328,394,358,204,300,733,307,319,22,501,721,163,88,366,100,857,60,804,233,656,166,172,827,120,680,136,482,185,712,715,878,164,889,562,880,16,635,358,515,893,819,788,455,836,839,615,528,139,833,435,271,616,469,125,359,642,833,36,520,90,375,548,74,286,530,5,874,564,566,144,186,851,287,859,853,892,166,744,844,753,374,823,617,32,379,766,94,657,82,615,38,526,398,837,446,41,787,420,235,789,101,89,110,410,784,691,810,156,497,110,880,832,3,182,230,861,886,576,602,695,887,22,343,454,784,522,726,583,707,216,757,877,560,734,774,424,433,166,104,760,880,623,864,442,96,817,324,357,573,173,106,225,847,110,461,391,275,460,826,173,196,727,655,537,290,752,782,826,726,789,122,485,135,260,707,564,321,57,682,157,804,46,766,208,820,781,863,607,818,565,449,288,241,78,661,138,209,825,838,261,31,297,472,485,341,678,463,639,685,420,892,34,599,32,30,862,61,796,673,35,89,782,681,778,334,838,307,718,520,698,666,615,31,856,330,533,32,435,447,193,622,483,38,814,561,661,406,788,782,548,511,748,516,380,873,684,135,497,257,758,7,836,753,517,416,563,808,130,387,292,299,591,219,195,407,150,228,178,653,694,527,175,484,524,414,709,493,275,499,444,586,730,50,705,725,396,161,263,297,166,434,862,415,138,280,678,777,743,719,340,361,565,424,222,742,264,413,698,877,173,380,96,336,643,264,698,205,618,762,114,99,478,45,771,83,476,105,845,363,47,854,777,17,311,872,110,24,861,468,828,532,559,397,831,354,583,31,64,733,4,599,13,645,435,136,860,442,450,865,457,737,607,177,794,281,185,153,737,138,625,719,721,156,362,402,834,220,575,302,489,357,283,480,693,183,403,794,570,610,693,298,40,587,360,244,232,397,820,346,552,12,713,554,438,56,320,751,646,878,492,265,714,653,49,60,632,533,647,289,159,698,127,755,851,333,424,714,253,8,594,559,104,658,294,857,340,292,646,128,273,587,716,268,96,892,167,121,863,166,116,684,416,682,1,888,103,822,48,741,122,416,708,400,867,327,834,839,337,384,868,460,340,33,616,67,649,476,778,738,267,164,384,651,390,10,704,629,374,212,133,404,531,652,427,520,390,769,10,538,682,384,131,21,320,331,441,685,94,800,892,71,390,546,236,302,491,561,842,414,293,818,625,739,265,656,57,61,190,71,50,197,688,615,457,146,519,373,249,540,135,580,554,484,665,700,329,624,368,65,216,750,549,360,101,606,266,136,87,626,77,617,843,8,553,223,619,303,274,455,897,883,441,768,133,853,725,302,685,467,486,809,391,11,564,338,82,560,851,64,570,879,644,571,479,355,838,331,842,88,414,613,570,42,14,219,647,65,464,664,365,798,379,85,629,436,339,100,538,167,281,99,656,400,580,484,867,417,144,611,428,900,737,338,818,589,323,491,649,134,23,429,598,789,296,77,123,145,603,89,22,842,826,443,714,353,751,602,852,424,69,267,110,57,756,752,362,748,653,131,671,795,703,491,574,472,566,385,722,798,362,63,718,601,215,343,581,841,518,576,156,487,710,738,709,50,428,646,483,126,818,67,522,292,198,841,298,251,603,140,424,839,713,265,231,4,301,507,627,510,522,2,68,274,16,262,287,231,439,380,639,165,311,899,540,713,281,699,831,21,828,168,18,759,337,887,467,395,446,491];
X=[74412963,1000000000,1000000000,80940625,1000000000,489990485,261205481,440550955,1000000000,46706210,1000000000,324958609,48630967,168151164,195428818,11492933,1000000000,60839959,26479390,440669577,125025571,382357611,63664042,250127083,94777170,345392480,1000000000,202163594,185503508,1000000000,20203408,1000000000,119741389,23366374,6042422,326159285,93335701,20387740,1000000000,956100488,327470939,105806136,212441828,1000000000,102386591,206715140,135547142,13002362,257258727,46026830,175005279,153742389,36072687,190908807,266144948,259294560,158310782,396715124,108221169,280262675,296350031,370102608,620552792,372245733,80141932,1000000000,558003242,518718869,99844541,166882848,193865612,434646982,219101581,32498500,63415458,1230364,104475452,148652195,1000000000,43103758,73521487,62634974,167047124,1000000000,134668489,199392589,16521862,759924899,1000000000,33556058,193517779,72580344,232871016,690591007,706497616,1000000000,165544882,1000000000,284549866,1000000000,141355662,5064224,34736694,393319275,45637162,32109397,181990123,20009925,127532703,129823462,3068220,473897664,10154159,209647353,330017494,4049640,567385556,121359160,6197891,152543836,318124776,72506274,124996426,89827660,191772542,19836654,87994878,917955517,16188962,94324299,14760534,679900645,150726355,131485708,96207224,5556143,589963191,119679707,274847824,32649709,248818814,351327224,152365324,1713330,198208062,213741630,72557958,220388880,50143504,58619883,61716422,3544900,325895805,177770840,1000000000,11824051,249548638,32403229,222301436,56619846,260080644,607477696,263737054,103907868,1000000000,331612617,124349605,904972226,1000000000,752666254,7461068,1000000000,15676753,253551115,332687152,145848245,54065688,295914530,169068084,93032283,180458575,179613604,242787538,797280855,36880484,1000000000,24917315,164484043,114955435,179441678,1000000000,531353919,63655956,169661963,140114752,57561728,402590809,317736997,1000000000,129580046,202555293,271760470,65844309,127830008,40225147,260864636,506327308,1000000000,359111439,198741703,60160537,136678258,29328241,73261557,526190568,596677,303200274,215800087,18086782,225391969,0,43361410,84707753,300308879,176492797,148912839,94083472,54246061,101198472,143400153,47831211,15095122,49250163,173388917,1002774,32090350,97291061,30708886,911997424,622125137,1000000000,54650968,352110745,90497450,441310511,142842312,242305225,71933893,97833095,135834779,164796702,165686004,156886828,1000000000,479760923,206667151,2049762,112977555,562510509,0,112917756,311190809,553771534,1000000000,1000000000,128633274,394683681,1000000000,299748216,5296701,121457059,195254294,1000000000,167033036,475076517,99993566,26207155,1000000000,305180534,137545902,700155,74969073,140744237,3823587,182978887,144427338,1000000000,121038994,175115168,191024547,71246685,737240507,25795173,25691341,301221514,355396260,15561649,81213176,163906992,169899910,285106988,18009607,78346934,51971383,152352422,51680806,129272602,19551082,327392965,515522352,676106731,253478137,198480312,236177855,314790562,358074434,58412579,53736499,55405126,1000000000,1000000000,277496572,392968056,143014869,161518766,18054147,876290039,835176536,17040384,1000000000,30407571,252095919,5069272,197208286,69704614,179121613,26130365,363337873,169815897,95322779,67202026,49395622,13976436,1000000000,684172999,33349421,208569573,87055882,52587770,795270008,327727816,114646440,260270462,9368099,1000000000,706922147,2340668,1000000000,192154817,143901418,547719088,286671975,49489633,119741278,57335437,34278915,97206254,101431793,185777537,175408165,104780630,53128946,6490506,348958154,227969420,231834162,516228254,35814410,338646522,39981314,7138163,341097121,1000000000,72366822,73589825,94744255,11103482,210260206,10435869,734548317,227933467,80725245,33428980,63272730,9818857,107124866,650994309,22421204,1000000000,1000000000,466160412,378985769,266784459,239237194,1000000000,202721,193190056,262845742,424815342,10264175,1000000000,168563796,4896238,1000000000,526824567,56285724,65847469,760414,295299954,20538101,1000000000,81236477,3348746,128691634,120630144,875039173,160859409,1000000000,367091079,92691628,44860768,113606358,232512131,55713763,343426167,618969675,878250837,18728299,5438043,76711031,154077028,570639194,175858138,230817077,159799619,852143014,267872129,471892367,185293904,1000000000,52808090,29170730,329431933,40967924,88371241,129765647,1000000000,18931806,9792413,110567573,95782228,393547161,189637814,1000000000,218835556,50964294,1000000000,133349139,721614943,33090052,632395161,163113851,55185571,3013637,1000000000,3880574,52158826,445146,337439304,217064471,27609950,302641157,194726177,179863454,204405040,1000000000,274248304,56740378,19394498,170826873,31453914,28831204,173072722,412802904,1000000000,67207405,46829694,67080945,1000000000,41043224,146131106,237261077,1000000000,683750735,211067085,1000000000,282399309,132008446,527934,87025026,112196492,323427315,35792412,30361329,36187270,34540938,341967002,86664240,1604364,357462891,13206095,85288730,235893641,75002933,30849420,18513503,122330956,1000000000,83219945,258301398,89889193,291635528,229459677,1000000000,280080760,1000000000,137614849,427740585,585527256,2809679,996780633,346729176,223362695,312883310,96418206,358728271,5757366,128325451,417944823,38327548,13969178,142678726,626347313,36775446,226258550,1000000000,83159435,3082071,977291,306279459,208339158,38481565,219029285,167966915,564317896,35338193,149440139,278806976,140274141,1000000000,142227052,159589890,1000000000,36044386,167751487,18588577,37799397,100201927,252098834,310622898,1000000000,3790396,448527453,1000000000,4273371,46854092,44515112,76537463,1005498,139408805,36251505,316191113,1419728,157557504,51986245,37650,307969844,135446488,58674132,460375834,82083841,1000000000,331613475,277501364,650535542,253860331,1000000000,212826836,191466158,341707300,240915513,430728720,310980793,49725867,570186437,138469649,211639345,14670556,70647194,247259890,947393591,196115737,68964921,1000000000,11448587,60017844,2175688,725950700,192021912,497175926,332233661,154447153,159312979,82244534,1000000000,9307015,102636538,392135397,256263742,1000000000,612286449,5523513,1000000000,153425864,102455615,156077358,229618324,152492564,23244970,289249512,12782724,1000000000,439126549,2576383,512269450,112897069,1000000000,27934873,133661122,760604058,532620290,4958247,447940002,312247515,525128211,427484977,203702841,33826279,23385779,207852804,56482722,5272912,104810059,30080456,192162087,35506259,456733426,248258263,1000000000,335796027,119550683,255748683,105792138,51131196,1000000000,598674497,1000000000,65279242,132665924,1000000000,235690786,187234462,684273286,142200474,2136865,184618099,60618176,24793891,25232894,44981652,83480992,18084079,1000000000,451967360,2805625,1000000000,257073581,233430728,27201757,16104491,36309762,299636,889666488,1000000000,48540728,800498203,10213409,74215391,57995855,106305516,36313379,73929914,6926191,322026268,58223400,261710417,62573744,110847221,259553976,253943069,965040116,1000000000,97065846,31312676,62304035,242975972,207545855,224566548,5023462,459446182,2905605,273488757,21048489,119351335,21766311,18031056,15258678,391591667,449131524,392912655,347329998,23043650,928969880,85689373,139198451,91951720,980270771,399919686,65222985,1975723,388210251,1000000000,115741223,183756524,240946103,428335695,44842348,737486,3909077,168958468,39517279,647226988,442993521,894092062,76739914,1000000000,1000000000,123181087,156499242,29631555,31321911,219549001,133069573,1000000000,197950081,137440186,532295814,126696821,1443101,478312179,32927234,74185704,1000000000,91811477,145184415,1000000000,2627866,502835471,70117603,46526032,38692764,8455876,272771539,296474131,663038178,294979723,444767071,62294866,1000000000,402208666,392177533,305587989,485866703,26850553,298672082,86171795,185480678,12308980,467893498,351419197,6576207,435080278,210248658,393732004,983848393,1000000000,542069858,389497604,253392610,17644999,92313502,385038965,437381812,184836470,1000000000,13282450,15193343,1000000000,187731471,110076165,82988339,200374096,173249515,685256760,330467936,279480345,23111934,134511252,849686463,322314760,1000000000,482241502,399615589,113857463,508183569,255925373,151657922,21965856,14235128,4601551,416569334,210485833,4674706,379548022,185510776,103549610,151018107,1000000000,235796993,873776468,66390490,265515152,185603641,1000000000,508902110,291904368,722309290,287298635,660972512,223561977,46430649,823161961,627190012,25185216,282244313,1000000000,1000000000,556730501,10784036,137194434,197612352,1000000000,1000000000,66088502,81263121,116522881,174945985,289832860,280062565,119244693,669275461,150290009,5182744,67861144,94674065,425069915,264603109,220147779,40853798,169924365,25443596,49053307,142504840,3907242,64677876,493243697,154603102,114511982,355285383,386813370,473124898,619071043,231432392,57931026,260402499,499855409,80924898,189048789,117534822,44612892,255460569,20548431,958829566,66521881,160904373,71423450,273775889,158398094,1000000000,217877101,202305831,225715981,181201834,80949153,40527147,217034646,867854113,18434075,2549148,1321840,11030482,325152862,24946234,383900000,3340273,140740992,2583045,176636994,149542364,100160414,104158842,26732476,50471610,11237240,1000000000,312292067,506237752,1000000000,625687998,138450579,72750544,229064772,92561380,169361061,1000000000,107963911,43003868,426977750,399096279,120822851,249444880,72422542,18642854,36434145,875783282,16147312,57480403,339665378,207807397,64038794,1000000000,6287574,276679489,101203844,27664770,39353425,179913711,78826970,382089463,310145701,455433675,22800243,1000000000,1000000000,604759970,36418146,123101697,1000000000,1000000000,106978903,20044801,417768375,1000000000,113763425,448168138,10574844,12505784,261708942,420495454,163409129,688285050,527399039,50202022,311972104,145106098,45298486,63483434,1000000000,569127469,421106702,285340795,10233815,999283220,461557351,55264926,291994696,40195555,19645293,1000000000,501442168,56349369,164373227,187694564,1000000000,1000000000,228397471,264557960,101877945,698022856,136177314,14219049,1000000000,223367045,640580282,17469889,113336454,478532545,64259709,1000000000,88079820,325204816,981251262,203221922,125441769,1000000000,210991360,205932591,247556799,250575457,1000000000,388360450,14874300,7299559,123005339,822582576,23437150,91525927,78921288,45531390,604026,90306085,47047243,926565094,93171952,507144134,515689006,384735176,301807149,454659872,135236413,34066799,57644208,847983,279533683,18630164,486622718,63168514,50924937,332032329,299581430,13600870,556687015,383887466,10782185,196905046,1000000000,50083529,264152416,1000000000,27277821,83615512,118212349,267196097,699294784,13689392,157218689,121299985,225160407,154524783,31693902,107402119,3607036,603453898,555832082,264517416,64044682,283044015,210537859,1000000000,75979222,1000000000,41701778,219742535,1000000000,528372101,81356560,915136322,1000000000,113544328,132096826,98233289,260802409,56243727,410814567,127301289,9430274,20947283,35886749,220161928,40893541,536220652,38326297,19541408,130695690,614846999,79447824,132919306,131885200,16170092,90354857,192556091,192443565,179993420,52291501,1000000000,82580461,131878705,79406017,1000000000,41624718,1000000000,160201605,417605914,78359585,299236963,46637263,10467693,109079509,644738314,293267351,12732231,332435445,29701772,271490800,162280001,378604403,11047346,79072041,147659141,766575536,89295404,136830986,326881114,667896360,150449097,70810730,71787254,381147137,5815289,1000000000,58554290,1000000000,11164413,8823004,1000000000,107483184,1000000000,5479607,191878295,688771386,200910997,142467781,355471570,94162501,106237764,30245202,38255376,10238697,152454953,280946110,535182390,742491292,27625029,168918766,218317715,200379440,1000000000,225180800,423937800,26475170,181362415,227234117,223005820,324013486,799424998,88211448,109536018,574552467,1000000000,630460,177395540,101911507,186814959,5931122,536519360,115610176,65657625,309038122,1000000000,21416929,166585295,47416212,101320943,1000000000,75873338,151739031,99773735,122713365,293198576,83377491,47711088,292288821,293039482,21824985,624165708,228657257,1000000000,98721305,423313351,1000000000,66230507,2649519,48489283,21613552,3725850,1000000000,242128522,41341026,336826138,63976541,102777967,395022963,212754895,88716649,85067556,160130646,381537336,72941248,189771070,153015417,22763301,462246800,128642977,293206632,413576686,591848529,335194864,117256063,216717194,942630560,5507337,7154162,68733487,276829956,630373749,72065162,388347609,236566877,385545363,86741220,97369638,17048976,204830966,6710681,912845120,279712862,5848158,20743554,278382556,180189870,4903796,496650700,267907266,270857248,135787384,86113326,529568841,182065343,12894690,1000000000,85138185,323326744,408397039,33635190,295264321,1000000000,24694247,148036277,15000408,407955046,842811771,156879784,129480815,221237070,1000000000,200095749,33284174,1000000000,79299139,149320142,89542195,148043853,44546307,375980306,119129951,133047292,124935114,4303341,231677383,94624131,226863949,32568468,75819249,379265047,444741895,1000000000,125235255,32931995,318238267,360941337,144769230,26419978,73061880,40489399,10286038,3138377,210328482,226626683,573586207,175252771,34860246,240617130,226607795,306721614,37931869,200910928,22436106,59136825,102166169,646727822,190232144,171968992,1000000000,644103159,1000000000,48701691,91023878,207131993,86375193,171185719,67516310,147539160,51342044,1000000000,1000000000,91375581,132004083,851447332,1000000000,736092182,288007219,259403336,1000000000,236602726,819427,141535665,127406474,196091398,150875661,1000000000,185963603,461282233,183632311,6429674,1000000000,1000000000,33073310,4141816,121477193,565092549,161805397,40902506,227198686,208139861,58541760,529497666,428530290,23013953,228639665,63036174,125590539,158409795,78667654,1000000000,815205932,1000000000,12060530,67281820,2887199,468440178,237756401,599164799,380803981,121611603,1000000000,421086301,847537848,11649494,23975072,1000000000,387829970,163787110,1000000000,97188148,210690209,519367,309730235,90492544,38472653,141398932,117583549,89834875,957145414,235520215,86004931,288122347,1000000000,50742574,763975784,28478630,81641382,110355140,1000000000,1000000000,5718846,1000000000,197095792,109402933,1000000000,5533784,336463213,1000000000,75036385,1000000000,125214181,1547574,125821040,25334762,380497734,73890153,79296732,2197679,87199410,1000000000,202219669,4786503,384843629,63324164,52297612,41274887,575243734,169297217,1000000000,82993716,36861672,494698259,296627333,166478,325553076,255335977,1000000000,103939801,383923517,32490160,184233819,86360795,3433892,223425922,111542815,775111530,1000000000,584197614,238874684,624235246,106282654,1000000000,95385940,1000000000,394022775,101603929,110158920,49762117,2673318,207755285,1000000000,50432891,221899465,24686026,120554576,781237196,218484503,162381122,270198828,20418026,23966129,5705457,1000000000,547051171,226483180,24270983,304872516,336125218,1000000000,61947879,10638887,476940439,23848315,1000000000,92411993,1000000000,209059286,1000000000,84930769,44265399,456308379,172562499,692559801,1000000000,73710659,235825761,1000000000,160639857,327214394,150679573,229750090,33611019,158247428,211872469,686069577,2570847,8295421,108295112,401116203,7262928,36919020,659170142,380113722,248199638,1640205,95055341,335851628,264965584,218209303,7544122,30287868,17900995,356840163,333945165,169218456,46188056,325241284,56791317,18430543,56527794,84769658,70664049,1000000000,1000000000,14296238,671966796,236720584,196946231,22185333,338769373,64262329,127300591,729799589,43319180,191651537,87932818,33203485,280970337,88596600,1000000000,3167866,588564389,211489080,337834725,95224808,1000000000,153433432,126927607,260500893,225679041,243802253,7135296,377741491,164185247,162330076,128997221,340686906,774829665,4520996,50823393,243451310,303130806,129539131,827760969,228383700,105627965,223791457,75150186,1000000000,45203865,92218549,1000000000,343994196,23401238,1000000000,45506205,112877223,131319095,41592055,366899689,100474003,368333589,26583190,181925931,63737278,375221784,133165887,4863193,140821629,55388266,648314483,102907116,19002496,383406717,29707085,399078187,515357614,17517223,136767203,25854579,439154546,514856737,294832370,709464361,229124189,30709118,860375003,1000000000,1000000000,801568283,265016,142373489,15115845,884218171,18701480,24353728,30840329,1000000000,689819142,140459322,50658470,4965189,256224882,180347210,62380085,296288730,420079162,403498501,1000000000,1000000000,182381579,24157864,240664356,200051328,23445779,8342643,93188383,110893358,1802833,158920035,24693114,102386913,39579242,132179825,1000000000,219421098,55384151,93284148,301974249,35992753,734228647,332855509,6919796,950939018,36664018,142690102,4236690,204482045,113660411,641618436,11170527,533846845,323053036,25176786,4169862,444601647,488580353,1000000000,89584940,267122151,4714728,55023035,302411049,357443508,416487037,110993591,86676244,159882437,293762516,149721354,174469048,218896472,24260679,144653766,124157662,54290280,181560832,741682351,32974413,434674669,64678153,461794042,81742365,142569839,6248635,129814503,187448515,3484372,40183671,113693603,1312525,3183757,1000000000,806087566,155887064,42765884,1000000000,1000000000,1000000000,136604020,761352304,1000000000,41759351,658510936,155728222,388384327,231643683,70538967,247701598,11352661,497284549,172486535,243933321,289515760,432964779,149329666,46320283,284407837,764116684,279430077,1000000000,182291132,289830746,23347397,123220270,26794580,187598843,3869691,111009132,1000000000,971669709,206282604,150377142,121191176,2931602,155218307,136656481,541606181,1000000000,265648810,97175122,1000000000,55947596,224950746,498160177,195422631,153508683,142401128,153048471,193957027,350906631,851048252,30612501,703571306,316413656,1004776,416019076,30390647,1000000000,17789960,371956847,914882,45462840,245563164,77879799,294974692,62951944,236946172,3054127,74176588,35824055,97008641,402642946,157179834,73760612,21354540,695133946,420016148,95340469,119957034,31370687,55180524,247438923,92195763,218581143,583513755,37921184,72782079,405526197,438372658,19029997,109371040,103216362,186331466,1000000000,650744953,268934712,467386076,185663951,90482080,125427898,69924959,174033744,645093653,1000000000,104365021,26021316,72951243,185603481,101480103,587537047,1000000000,37414696,294921154,37832638,140572800,1000000000,157655451,266435160,185975696,221640176,171118329,166389185,188158931,118190542,118772088,152736203,47923123,5720461,1000000000,38132566,208822687,70654191,251023748,29733305,52273927,394376783,122664777,459703724,113853748,32450676,265168798,24738691,879538647,1000000000,100304915,527572404,1000000000,310359895,10111815,25387331,185159551,210344930,169898807,64668934,115062690,114028116,42841027,83765761,540528348,81287139,574982292,1000000000,8808251,155729671,167822794,1000000000,45474202,3730987,252313101,28026359,1000000000,23405890,93206828,128322826,1000000000,220788057,152671315,117736948,110892710,19482872,41709824,109798597,184533673,264345534,98521947,276762727,440151609,196790021,267796804,603360872,68721496,284085144,195270279,22826767,12201539,367336109,56173799,26557880,1913603,4738141,55063138,1000000000,71871989,394520054,474316716,79190423,23714015,215136422,487112749,356247326,186439552,14703800,45265805,361166134,380362062,1000000000,145938496,36723454,377600480,146514012,1000000000,171001181,203858352,654612163,203470377,715302499,147661957,532080310,609762673,1000000000,349588362,455480392,85910917,466042850,1000000000,25034381,136393994,20791118,176771765,200806265,1000000000,1000000000,19324909,251520540,147831215,120429657,50169440,153974842,4631007,348029967,1000000000,202496916,557201683,283845613,577737137,131279000,95019106,180260220,201462948,157174420,1000000000,1000000000,329432331,1000000000,274563143,891868515,1000000000,234581451,129165082,195370549,14472831,434868102,370190,259896314,195855906,180770747,265412956,493405272,43754608,241402509,11081151,16674211,36880103,21614912,25066305,232600175,1000000000,890095361,10229750,141290423,126956141,320479264,133344675,132389946,186058005,89023905,418863953,1000000000,212498234,1000000000,57335077,200668901,550935211,88735187,100311705,205693361,226038419,106142222,1000000000,401848031,60613605,375424778,42065056,125332585,192678405,403322898,82517532,25333346,7416025,157844343,123885568,25469319,100280564,437080518,44884612,444785812,138427870,1000000000,15747253,446910643,1000000000,61228425,386774813,1000000000,30509530,416780592,35568835,130837425,40418964,710550075,16678074,1000000000,63118255,123576110,174386453,551288973,1000000000,881428582,64048440,177940797,27516569,7343819,86677554,10075934,18690788,148422705,32418320,250575657,1000000000,761546445,201489010,87278043,333297389,107375214,250271225,19298561,65405364,286723259,74494643,172285295,167944993,219202517,554609836,154372014,257400714,295736439,94524958,376010690,716083760,110367039,38866253,1000000000,52716679,243157112,331632456,1000000000,1000000000,66948275,360231988,17214535,65725854,66977326,18960507,486269083,1000000000,101209095,23371556,568499477,100492127,539305489,410302740,350754081,269847181,623541396,290192141,394170154,564964844,984071958,223457896,203694209,141708919,119131805,376113778,51633702,171792214,1000000000,115362777,1000000000,122320311,65629446,1000000000,4056593,59238977,93232749,39794506,105874105,669212988,601875,1000000000,87469981,307498777,268690081,1000000000,346148920,69357892,121516337,27731974,1000000000,94886714,12264242,220135940,927931369,180176696,58128854,170754875,1000000000,5084016,58655215,93970489,279165230,409633164,584528002,8609930,88533436,113963517,293657818,332009658,1000000000,111677362,65680280,122862410,169864602,154324083,76144336,151497681,332034996,124045536,372558773,101196799,78063746,215652351,487999638,34028460,10994224,27118085,1000000000,1000000000,315155379,72512803,454648100,100934733,213541945,13453200,706852057,28189923,311572685,654468718,83950043,60609803,104820268,89093648,150154237,406749915,220497112,179906180,1000000000,102147677,1710085,20702091,290714035,118016312,3851297,1000000000,402501262,484379075,9139609,198710673,148432663,249045568,424678488,292138361,110764563,12794616,126723947,521571189,56903206,98381865,36460090,84423965,83685955,3259058,52779528,1000000000,1000000000,29346394,293614270,50019165,275990416,6175977,970030,160070528,168327044,443368158,146777882,145881764,1000000000,105085674,122826150,1000000000,1000000000,1000000000,23274815,42354284,25091370,267676018,551838587,260432329,17160023,61519405,145140158,25844851,38201334,46181835,203873464,259510964,244504417,12536358,80247774,49420488,318542958,180499094,151687860,120268981,141834315,237039855,90937733,180606248,53856954,216140805,4685564,10039664,74304465,214507196,43308429,51389147,49154016,134359819,1000000000,130449297,94840225,46103317,88468446,452779706,136279439,114303356,15995149,394430340,133767893,296618690,104435443,141982157,205092636,5511741,190991002,361586015,291056017,28989090,606093786,733271979,69324144,77520384,1000000000,62595100,160587450,169156560,14035486,7812879,85456874,162211885,364496795,140052200,207385825,44148267,144751491,345026067,24068604,202406884,208136958,81210039,201285666,639922993,19271922,247046903,266131166,542701,217068636,275282006,1000000000,77767258,33603699,359169155,0,21080852,324309484,48160998,1000000000,20316503,21995404,71551176,107566896,96945728,63682497,154412982,93311142,576574757,1000000000,98684931,97599322,236165498,1000000000,782004805,51397519,1000000000,79557692,1000000000,328431538,200059553,41577273,190968781,346147172,137511994,98926692,90234644,36506847,9718386,84982056,20943834,109163444,819252684,253388090,314511308,162369105,150860903,131195537,369374885,3930568,176562552,194511632,1000000000,1000000000,1000000000,279233860,12558713,209369304,546432746,48976161,38104938,108354757,124132429,512811718,38056684,115582567,13878920,1000000000,497952847,3964734,117180070,464954392,117568106,26300439,1000000000,4254359,49907710,511418051,218546811,763166418,109551640,2728398,50338916,31619306,6058332,55873335,1000000000,308160656,263273189,1000000000,531241918,116155255,151304558,93612424,41226528,330767625,437954112,543801115,422875297,3513172,211708865,261393700,34552452,268620595,30639505,152204120,120607652,59123433,936379,185193393,54749638,225445650,24312846,141507675,1000000000,73680801,1000000000,39195889,29825392,1000000000,206808734,514808726,1000000000,343471451,220071760,34059378,8375198,52756181,384763303,350083737,247203882,314592344,190005261,19336509,861278530,164030729,51643406,824464914,220720585,1000000000,55995691,20796315,212399586,247367706,167055878,1000000000,152216367,219013154,373589000,53389226,12253520,39730439,541401880,406479204,83713567,412609120,2240310,1000000000,653079803,93673724,79107519,366064357,110117053,9783504,1000000000,289135251,242207359,2213104,319125115,99042467,1000000000,179698278,96149292,123283835,345185155,1000000000,30375135,499784785,361798134,67008404,1000000000,732630864,48374244,1000000000,405237482,33082264,61158149,483949217,68744055,18675603,451896137,1000000000,17882806,99849927,163459649,211502515,679442820,40955086,125343314,1000000000,173607079,17932127,251016870,31505435,266373449,190248940,171805003,42577284,229909467,227880770,32478868,761484445,55793804,116240215,128154392,575152,731432688,23896751,3978691,683166276,212300048,58738006,795444992,473578197,119240428,186282343,437040665,1000000000,108216225,431640625,3361436,148493283,56353801,79959294,189474607,948154926,541336032,220330024,1000000000,119517543,42621329,621560942,1000000000,4804638,7198551,29032406,65048710,74913777,66695281,78885261,185166728,1000000000,29154318,51475293,362949623,211803227,157352375,309621567,1000000000,219978362,228470724,12395325,540455821,164952718,218454877,80056637,1000000000,212286903,225996066,1000000000,59883933,106513728,20941295,418092364,82490775,60212922,5517778,330411217,87368234,48243254,191208909,353905157,1000000000,405754,295079158,313263039,133518065,1000000000,28714796,15016361,278727837,150857659,8193374,1000000000,237488561,228140547,653544912,352038561,23444744,1000000000,20743743,430088483,40535367,180588491,89971517,386867055,523432093,1000000000,158166096,13076911,46140014,1239493,201804927,112228962,217364275,73437394,1000000000,6271035,47184138,133094974,57124063,39819262,12352587,319240380,1000000000,362329930,183973368,649458434,357480279,189941590,131485340,18987824,52023555,922876651,28156176,1000000000,46848430,22678824,1000000000,533973026,79441098,1000000000,73043790,328166460,72465724,177467315,64916904,13617689,904286446,287647525,122482120,274708045,850887267,179164302,323979579,338270779,106975327,148797608,163019987,275961450,457877693,243604754,422336079,99831738,151467731,301265003,1000000000,472924179,308601744,504449131,1000000000,331340630,64323157,173933238,1000000000,13123368,122254737,111992644,32161799,366614583,640994108,168646708,22059975,591210426,19943769,5620913,175349037,129482688,289461841,448366427,16990456,100383132,1000000000,401229771,402597393,101710662,19391861,95354891,323453012,638533861,35655061,209726093,56369755,137691274,201387786,1000000000,119145846,9210056,255700817,13221214,53714493,233159460,300774271,125742310,84110746,147356008,105667757,33093224,1000000000,200018138,78949836,36640292,337607416,755257621,226318289,241853432,712718503,113467566,76301979,36312129,713467416,108406701,67097561,1000000000,633287531,7733233,100904578,1000000000,94562975,310385399,182286066,262916758,211038082,478784226,200135780,400940545,284801021,82103468,71299926,140690870,47121234,626313050,15019054,16239290,42237253,422675325,136542276,246403915,385446597,90163707,7063659,152215052,165541960,8914314,163939458,299569333,124981246,1000000000,558014353,30695711,964504332,117981272,350989951,428576436,38541965,124759587,251107314,169336321,23415130,330772391,128752330,546989499,5370383,113545630,221307226,79477605,485273249,37444949,39361070,199046378,41820443,53581553,199182023,256087662,195464453,13907825,311796271,35503906,648946206,85464704,40680130,21647002,26114799,83188576,262410989,98136417,495017450,11579060,149091020,106589982,60694864,130103821,304926621,101994232,695996777,103687187,519548312,226141366,125189267,1000000000,1000000000,8940633,26055160,12268768,55870505,407319982,210245725,188535252,32500663,129577149,1000000000,4879858,88449215,6049858,1000000000,1000000000,73304860,102226639,222172791,202983111,17356834,572990407,60642639,55418371,124664420,25982092,158496381,397710419,224763280,566003487,188439940,129122039,538458642,732330610,13745934,667434912,86548646,268673613,594323584,49312159,347725244,332366345,347707337,99709646,1000000000,698265226,365247460,622329313,60942024,282142772,68237822,1000000000,1000000000,3610000,324208018,37864539,33730292,133982522,1000000000,191213822,201614213,58038934,118248674,1000000000,216560575,14437928,37691326,1000000000,136075890,30617192,116860218,264767987,20066976,2089653,22676918,95755464,418575161,14758215,845305352,161944066,49586161,247076330,137557785,392318955,61310359,10734633,74705242,45881631,99846933,815712371,15711030,260747279,47877304,146631202,1000000000,918305067,1000000000,144509641,294783466,138660659,425773065,102036653,1000000000,160720263,33846515,505111386,158578486,64004377,1000000000,6984618,40511725,244207236,853842146,826020409,241522174,1000000000,89472273,40433396,6829951,54308933,398372879,101000988,521236787,39586772,128373253,1000000000,1000000000,275730190,91395075,136968412,28000431,12566354,199731421,482196736,802407493,622456097,67092362,498605594,345293480,88978411,1000000000,45034976,85255153,294187480,193851858,162521085,32509191,94349857,546421223,264794519,261633136,1000000000,45941889,96815250,103264252,89253684,219850736,128681245,54322382,39677654,90888765,53604123,114483959,2267833,358460968,341594063,144201087,788498993,1000000000,143488162,1975999,9243393,242685555,112077136,124342199,134145951,203657292,11053709,39496987,151380890,218130899,142667672,337474476,34913674,76142754,395566475,181499819,57263077,1000000000,1000000000,237274425,7229850,611959603,27437851,60051952,7554289,39698412,47602211,74814372,700070932,498082591,753418074,483682352,50178582,484015,1000000000,178596622,1565278,453879209,1000000000,114803900,10371355,189360273,33515095,376814937,39322685,107008669,7822523,61271982,413766822,321731475,201717088,38851931,187553426,657050933,192063112,212790722,831401199,254307376,173478729,227739940,35627046,1000000000,925125797,37660139,103464428,1000000000,81130728,47393546,100025316,54128851,217548771,104643884,112475313,37324624,74437951,131421560,39697810,31193533,79649239,216544875,1000000000,427624423,93989198,26358464,198866638,486225979,1000000000,280980864,374737287,429488536,53390940,51891250,650040638,171806383,240060807,560582014,245533287,57785465,60320617,551245097,198078251,359258436,43268509,422632544,135728713,103465248,1000000000,47755713,69972667,35201999,1000000000,129968144,10432878,6374617,155189249,362229288,100974286,86191569,194398571,109924357,577090376,18362506,377876133,22295577,114780887,1000000000,714880,1000000000,100279349,54349695,80006689,124388515,208091804,33793219,162826253,305058168,34962635,93334735,1735050,9978716,333905102,78917053,1000000000,355187217,120619181,31220298,410228808,70175253,727346873,1000000000,812461185,129818467,8116306,1000000000,198460371,153613394,63295323,1000000000,7479525,137939988,351147001,1000000000,83326084,1000000000,30096803,114047328,3190879,72883331,259644350,165917721,302517927,531010249,60901283,1000000000,287497739,763217043,8654537,500247085,19884291,435125603,1000000000,217026327,54082787,279660469,116004809,159368705,86903456,400356785,233477,1000000000,187023807,65615366,540385283,275959326,140252555,131405245,38916540,43497892,152961431,1000000000,432938761,5028854,145269197,350845895,98914818,88000722,21781190,6516700,137521554,80068483,1000000000,357599327,126170799,401224010,341908491,87548265,299377767,6870705,770504612,69640490,173584853,355002720,615527445,197498484,121974995,8686300,206284427,310812368,1000000000,768851464,526769182,115492874,1000000000,635188,88650779,426326015,24908495,90522108,416381039,999726676,842708,227811829,49084661,92223915,5269853,154960127,180282673,67540343,385595503,254296156,12587107,122112600,70150793,92312079,24289768,85116689,1000000000,64076729,42907865,1000000000,1000000000,130767204,249514,455445632,7970886,206349988,1000000000,104558106,12172113,20628111,1000000000,526899566,216587948,48512582,118667339,55283256,51490306,108078394,171667043,62254778,98355620,73062947,120281982,123439531,151826174,104925046,17756131,62418389,26628883,2419902,4235887,817462890,308259256,54922915,127964442,1000000000,251421265,622665827,590172675,26393836,48877566,206164089,128632938,190004868,16923379,6326470,135419875,252253310,176141234,84450180,845867760,46579588,415687398,1000000000,537036179,127838174,161536574,1000000000,292590201,236369906,84029543,274670776,65050960,229060264,43815286,20918352,153638356,97257713,256105771,365750302,265751143,381252433,314484638,7846452,37221195,163330993,418423392,327253017,32775158,4053756,106551317,164293708,8278206,1000000000,257931710,1000000000,6594760,216260684,199458510,412885894,106002059,80807079,102496140,1000000000,133117994,208767456,1000000000,40211761,38424074,156363495,12898178,10463727,900615956,17132927,32434453,203448502,1000000000,246621087,16247335,20299704,184279498,77007712,4501236,1000000000,13115540,348256441,377895696,145551093,708471103,30072841,1000000000,198811825,208613801,64770640,2298954,819194920,75662113,1000000000,75964661,84425406,90194100,103361908,6874025,44598841,297230193,42152487,1000000000,38270056,84894220,444609975,226437062,1000000000,12097023,120761984,187025545,31574447,177402714,319876410,25607478,50280281,82659320,94800380,193120808,70644620,589773694,357583238,1000000000,290334667,328378173,78954684,120235754,43315693,1000000000,309362785,298032292,76708681,82743143,1000000000,245778751,131557875,134459111,260285809,55229404,291334796,573532049,87514868,564508588,10927659,122952512,51287972,276169012,142513668,246630449,180186722,175125042,240674174,128961978,35401993,322141557,304287782,88979003,416171791,300215374,88690804,43060264,157087616,48596849,4563927,32375585,435018260,1000000000,410738409,50580616,44101206,86555988,273164271,30282442,1000000000,787177936,25702110,65296097,284752664,544645822,409794068,57235568,355506830,671853467,219064222,187452335,204885087,1000000000,70412524,34429352,5431665,971515168,49594040,1000000000,443237612,51308690,231112930,54649037,1000000000,142442743,912494202,846258985,350425545,908966387,479308721,184723863,1000000000,35885041,841275768,50679864,566384947,5425561,376985027,41263463,65475159,21312755,1062077,293328199,360914761,59583939,116156654,230374208,1000000000,220479117,37713172,1539899,86402521,374782081,273927692,102357702,381210484,922390824,106567623,58385331,19414449,1000000000,36550996,26653586,53830636,35239945,11812168,599066011,1000000000,9277557,1000000000,32251131,83184655,241156147,39541903,84890040,1000000000,21855956,88621508,1000000000,240498392,148363759,65074438,6342746,50418379,117743177,71302122,86199078,406445314,1000000000,5882383,444313972,110351386,201157264,196055741,8521897,50066380,21785929,5170129,7891918,488976989,108713657,417191776,60221628,414579727,495532203,68949452,286979445,367437692,85670402,462511366,293074675,445075272,1000000000,802113307,459058471,102407780,281514277,14232227,1000000000,353340200,589190580,288669249,27975868,54556724,5331832,766282867,15189798,3072659,35921694,26073948,57735382,53568182,493262749,258476025,116586850,94635479,78698458,1000000000,1000000000,304446961,236764167,145403669,316584259,727177023,34930553,316279662,68051537,1000000000,320806710,258239625,435590930,689146129,42407877,367198239,135835512,1000000000,93461804,23713481,4870747,608667867,54365363,18100979,19263268,32716936,106681011,22166817,103370288,102667418,178864900,1000000000,358169716,134434493,55772329,684918616,493719043,329786057,1000000000,51795102,3958280,370006353,71935973,9632670,1000000000,663064205,1000000000,28190919,271498013,1000000000,314307392,763651735,190763128,19038178,1000000000,368576798,427586391,52805774,300667791,155786238,1000000000,5044502,409644009,261955979,1000000000,3814018,218977305,26731412,517908401,522864124,88257974,169669742,7055403,3842392,221384871,69212490,260650903,24567745,142072079,727435672,1000000000,163386388,135238015,73343392,48426666,12364395,64892480,122669645,69958152,367701720,400681018,173083891,12087604,84928308,697777737,69168105,221910251,45622688,31293691,57939111,574547906,31890556,74539275,151777373,357139417,82825169,314859755,76849807,142837819,249843756,245979696,278587731,134377588,33341598,371152295,221706307,17960345,1000000000,15794014,56341885,190127412,309363899,1000000000,77962110,234929474,328296638,394342900,864311275,269826376,1000000000,36028415,75473535,473262612,1000000000,74419192,179337819,814091906,122243850,159142382,43318496,56840175,762480824,77061920,800368,4586189,113723124,96200636,360890854,224653601,29787662,65290497,106517005,1000000000,30445161,50664323,65584068,430166542,1000000000,46013827,94790981,1000000000,339313236,287762337,201080671,92625743,74884887,340924276,1000000000,127873679,38030807,675240842,528109329,8150138,66903355,316390406,156011119,7013579,518653195,208762422,390838022,1000000000,181712292,100259326,13403713,1000000000,1000000000,66597153,17279029,101148476,21531765,5525242,558196501,14974929,408110615,20141042,128400128,86959997,232470347,1000000000,1000000000,324870190,277278383,195016023,49558933,19367122,104339908,84519658,225423599,1000000000,1000000000,223151851,547413,88318903,1000000000,26788201,36426856,1000000000,384699290,806373040,10470517,32530119,376684060,2716104,168375346,29575238,3153103,942501200,5648050,153280274,69161546,871298651,21186700,487951972,116342300,18720756,176700378,299125399,540538,18767158,26868828,280186793,112514901,27153440,24708773,1000000000,6703755,46943137,8790538,240642040,342830551,759629958,592553011,143648033,6936737,63334778,210211287,307784806,129521062,2996138,392895068,1000000000,577404506,245331501,232291607,1000000000,257761306,277408741,1447966,1000000000,11960265,166316096,10487263,604339462,45220929,131424700,91394422,241390486,12310221,41547016,41122597,224329553,185312943,1000000000,148786184,619090234,34662555,579473182,55506666,34504427,2102156,503265366,104580675,58051535,134632159,39852113,141382799,2195001,254205381,202279398,314062625,220682672,256190580,497745745,341496832,420146067,213152150,295688576,548600558,974483969,106857330,18412497,530726106,773831598,335740161,287438779,117416064,23031318,7787929,673974600,649985197,123655440,161437846,494623442,5638409,53879976,3134394,113051836,34903135,1000000000,2317612,983888511,96680521,41785971,151648836,30864910,247661284,255571497,590108,341111564,635803430,98286615,378683638,108958439,141618265,15586219,98021082,202496639,1000000000,74212930,109769760,599291866,66956800,434549992,54147442,1000000000,315570483,62661948,136450143,107911161,297873070,16869607,219262495,62045149,48739928,175210482,362970334,392807745,40376966,511828628,30878883,928513171,18036489,36482986,38010548,39032683,42982975,245718051,1000000000,17099287,1000000000,198554140,755129974,1000000000,1000000000,1000000000,395818308,22180454,190568233,1000000000,1000000000,157414611,141851549,137013678,1000000000,277141577,108943112,115840515,195671376,56805872,59047293,204465546,81098976,473050543,98621654,219141024,22977015,17835947,98208459,130743556,102659341,229956239,1000000000,333039847,1000000000,531335606,9648575,103479294,219682690,94619733,93192325,133198473,1000000000,94559637,281783847,88461793,498222810,504108394,62742350,196375056,400273775,124376463,134518333,171558681,56308995,469790715,269514595,355897948,290192315,19073669,65618124,19369847,478386480,292267405,1000000000,205333676,36425127,1000000000,29448540,850490294,60538377,490700368,60960887,1000000000,240586032,600182340,542385182,31896206,31895628,29231582,9252846,51568056,490633514,331303516,301295806,96753741,1000000000,71618884,712884498,437505784,131683397,17570951,63971776,1000000000,22564056,1000000000,442108221,101411475,38613800,67542895,21311397,443442919,245796347,10764406,87400617,527745547,29644327,1000000000,496206029,1000000000,238687544,22269449,6882552,92946091,131672852,214668949,141164685,393912533,285672565,351016482,307956479,270203657,258382287,234910413,4078542,396364419,48018318,340885721,41923082,5750331,127354041,127727574,305868626,115156747,427914338,54536270,59670189,746757801,60463045,19345734,1000000000,1000000000,212291,56689374,9989643,112798205,68945946,107234017,56450540,168329441,638565281,3786746,270284404,77130385,411540696,288629560,106369174,256259212,1000000000,163333988,2551155,105996190,1000000000,12690977,134736173,1000000000,282684484,34798507,87198555,1000000000,64564134,245846041,23420017,1000000000,52399165,285548135,891788346,109506979,161374464,471779576,327319675,1000000000,430017175,139155536,576248300,97696868,90747982,291995114,75049372,1000000000,56411155,313840861,277157198,7736698,546429544,2951987,14489295,314013066,3687929,175290716,1000000000,136169903,46205628,146417101,63184673,1000000000,38511490,495002719,546583691,93780957,1000000000,29316467,2845730,566976965,136026508,66734414,65720803,801293825,232885060,148752561,149432477,368781712,1000000000,58071584,1000000000,8873205,277038420,77303911,1000000000,55748802,432520423,87430124,32499870,86776960,243993853,272168947,374721016,1000000000,126724101,27088375,4271086,39691644,47910360,62767906,237461489,1000000000,266598372,174592404,92487240,239274938,270893039,405171649,239516719,345881678,163534288,712227375,148576902,15129558,65622884,190176937,398388426,105134034,162214164,1000000000,82196731,105932495,262527075,325968658,40663322,113133536,228231839,1000000000,1000000000,40007817,196775775,1000000000,1000000000,131474173,562534852,26727241,26154488,30599376,633806253,258260028,50476052,91914589,332547,14384466,27841295,366808244,276295210,206014616,1000000000,418685020,72853535,111091408,30896838,33166726,441038051,23918199,502630767,128319777,1000000000,404626159,11138579,1000000000,319391674,463653649,93806208,1125148,236930063,721790848,58895521,106089349,1000000000,1000000000,99746241,636560314,153068381,506746585,125827303,229102130,142179500,28030381,253793127,186540750,8344229,41678247,441907929,164270057,391903002,1000000000,110227417,229643164,371212502,41704331,69470912,1000000000,12950568,284351414,334384152,294144344,1000000000,1000000000,220097509,255576306,925626769,30502281,79719482,391736759,393141973,194197978,1000000000,493428796,305210262,98541364,847104421,89779897,171305728,1000000000,33196078,266710774,197148591,1000000000,418228038,118265014,835879918,546739610,137212902,893908699,16906591,273792394,38255548,9806092,26667666,705807162,116866464,136503371,145266062,37027378,12755680,7698534,43629852,66401457,125875115,234305727,206756386,143731389,768227290,42915702,211703050,86402588,45350709,87843146,15787320,162165248,183220542,15700963,40688529,1000000000,36788018,55093817,184960698,71015118,244686960,335514516,122244327,249586633,1371554,125096952,410050974,574973353,335117860,16245255,120145419,66638251,25176670,88869396,193873055,3533484,59265612,318020737,89519183,812212453,21960959,1000000000,93207875,1000000000,3205164,219694225,1014801,197097157,448399519,21623568,62665662,162275441,168813909,234910909,399772219,269079384,94788299,1000000000,600869081,234744210,194415061,34244012,14157171,150532228,99496758,238025782,639747388,1000000000,139635912,920604280,22345964,2217266,138195889,109644273,1000000000,1000000000,210848949,567078976,121517145,1000000000,224956375,30415704,223348915,112992074,148348334,38727696,34605229,435216442,228091772,22222681,1000000000,78687592,247681449,118474575,129695040,109493002,113431805,356784978,688917113,512551665,174878311,305996214,4803554,154769617,256017674,507448576,229013737,83125792,9039413,30413053,18576936,410285108,421460327,10991914,12957018,22915754,1000000000,44811298,198267523,741048740,1000000000,94390614,90634746,48826540,21022282,163590432,290159715,480569225,1000000000,1000000000,162446429,210410912,1000000000,61949637,134696794,38183807,809512521,422893075,170705316,33139172,163748281,361420955,1000000000,1000000000,45838021,1000000000,976188431,718681600,320731326,85056350,1000000000,744540608,243973815,1000000000,892636228,41849474,104566002,1000000000,12065866,1000000000,226484850,574198864,241516767,60995543,88161347,148370271,1000000000,40985777,1000000000,66955594,256420770,1000000000,98564376,14332713,98291381,368378743,102283611,476495340,84699916,1440618,38837292,1000000000,82397599,58265596,913875958,90762388,111512590,1000000000,489197072,421782450,77709124,93157809,142510795,130804687,39625006,125287225,317160559,17243766,168326422,557517453,10467561,68736203,338426013,313541351,29232382,137401122,27055040,1000000000,109153122,1000000000,54154656,100522317,35531176,149279720,20894660,44584391,9411283,280712233,111281479,166974805,14249204,51897209,261750286,155600837,406023378,105232663,1000000000,16860902,275473753,326196,794026531,285507471,411165252,344716456,84246737,21726634,393956155,61976310,323092361,50331962,43163505,659585123,146639176,84552070,268362596,199925884,123081327,59740949,344206708,33999220,32730310,73425576,277382120,712974235,141294638,545622569,1000000000,143186707,494260427,28886449,57318613,28604893,64889525,43956710,443822538,324108278,206676900,117466695,45500592,89416916,131827715,7803580,177392178,1000000000,38504569,55647075,173360584,95788882,252816423,203651450,1000000000,481153269,557770014,253682486,31807166,337270269,1000000000,1000000000,1000000000,72894293,25977896,94541364,163601663,1000000000,14283703,61274740,440558759,806870809,210475584,165385389,266669242,39067037,251533361,49923923,1000000000,1000000000,22949527,151396133,126463174,243046919,192636062,533709109,928276207,160862532,319258708,23624496,83684117,791396819,117045174,19408365,1000000000,306038197,152448607,288049382,127476945,53411744,133684478,18082957,73149672,69264240,11903437,15985489,110135100,66949080,91292496,47790,47632286,25326847,2026674,1000000000,1000000000,181885458,76441553,227623036,58487282,52146740,141242108,26465724,168344932,56175930,117273727,474111954,584215081,25032064,1000000000,113563554,7513767,235085896,368060079,1000000000,430478375,198372161,201304595,196565037,167219686,34815196,58013440,43178985,247947274,253338413,666521119,48223920,1000000000,125649655,91575235,70681653,237822424,627305547,172997820,55247538,3224462,111548750,11787836,589108355,226598284,4264628,171113337,295358120,823975084,905708356,57819110,63334714,1000000000,425715617,1000000000,175773849,22514404,148012715,1000000000,349828293,1000000000,126077683,56849952,19166598,340219,91037683,608732464,142436692,31158022,92109197,321840330,391150304,347871373,93337009,565910666,1000000000,49976370,171170694,930198206,257168302,9741628,315050800,367102087,295638634,18416982,28617487,598738423,243560536,116834090,24714197,7385665,281348152,176685859,58325643,307476861,69082385,105700347,2665470,64663017,109752273,27955910,5870692,37685412,97428030,465429335,64317268,5879974,124845246,29199126,329094374,1000000000,24245943,174436592,25562826,35741285,21419560,2478316,57143643,250104510,156287457,318071808,72635422,346903640,1000000000,40412711,245887942,15807795,198987978,755260675,362721923,127112918,181971177,50838538,25180552,166936375,315780802,8954269,168396671,127242965,131854628,403956512,845661238,513393132,94277613,139333569,17532081,201929344,578155724,958750520,231443625,260303536,188272104,788701495,26785902,469876766,189786311,491762907,11454286,62189626,191334182,49402060,148503820,36340909,1000000000,290618054,409429076,50584185,183791665,556643082,56883682,1000000000,13559973,386059097,4443205,131642302,302568064,43437128,63350657,217316277,95368306,1000000000,226036695,169291132,19480940,13388744,74434119,88758482,492552265,92328929,677992849,50047423,574199637,603782812,652226952,732348595,128473976,200957621,41628271,29776202,5857098,443395575,55932726,66761355,29100205,334261601,1000000000,375137801,407708533,40725274,39398888,255042895,651777126,72951207,188915799,64750331,155201892,320580968,16659841,8275692,199360950,393227477,236734656,5775790,503179717,82400035,1000000000,188043430,236029147,202032426,86976245,24438830,35714518,222417691,362135806,77441579,133002608,61795539,564110205,446524,1000000000,1000000000,1000000000,1000000000,297103158,830576578,176214388,156305747,724998390,44981849,244152125,1000000000,84714071,179319075,302799203,140257386,206248637,70797517,29427559,71363641,714367374,232154795,1000000000,17179875,218700838,1000000000,49084631,344679038,401287710,230001928,7945471,43958644,3088253,144353803,55113598,38191541,52716759,261383474,110465710,40632745,273155456,168165836,19544227,179978262,181005574,1000000000,56797206,48034724,41202548,179008685,2228524,1000000000,7062511,56927983,362394305,419472495,336540485,153995493,327304984,32339825,797688015,127510708,190181543,299250508,392602545,70999370,89400372,104563797,1000000000,78027886,126657896,644450192,57673989,178032788,1000000000,36180609,1000000000,71544624,216710624,168406238,188679996,31552068,168246334,1000000000,1000000000,225961361,153545661,295225433,45343259,12037841,6356204,178620448,23500381,235391526,263257134,106349156,437895291,43149207,274112889,47481761,31976905,652024496,160868306,158765692,17032618,87222450,957147801,3588155,242238296,177659124,488562651,123504322,1000000000,203694666,12380687,16089127,265029612,157479018,350258157,9995942,1000000000,164084354,109626815,89843411,539355881,66266586,237758531,635367364,58570078,62721180,140701755,150566315,9428480,1000000000,158962303,56644388,10139042,261189958,84812635,25800703,198706466,30027613,19199367,18114605,95285431,216264155,106342619,53732921,35683191,11795254,42042379,408914174,105246503,216831007,74359021,13980227,29628434,109119945,176448881,69659,176355673,631468492,55007834,147682127,47555198,218122450,268961638,136644839,204136296,361633639,44529437,4915280,131016776,740042779,18888498,180013562,272541437,328589179,54470924,34540319,61086621,274706908,221674587,90882080,437871781,212235516,76518235,24557386,367052799,10442637,295742578,614209900,103843242,1000000000,164070045,1000000000,6166137,145180698,366474948,39691494,51886371,1000000000,1000000000,142820006,306643015,281223853,13812246,733896844,202007353,41577483,337753797,46790149,541608666,19874556,144346432,631630667,10762665,54021353,148994300,1000000000,343625751,61772734,346761648,55558041,154259833,1000000000,55265444,1000000000,74530098,10553444,42380134,65946095,240765481,126991522,1000000000,112621957,431515962,160092449,208568761,254461992,17978986,139651,3169499,222839146,121645944,371909750,35620028,145640150,1000000000,42911773,60095959,64519814,381752680,77008066,1000000000,153714994,230025183,18316981,489473827,150328993,350413791,430089609,227376057,25578289,193181140,99115814,1000000000,57547075,332284023,409337940,191550329,164666986,2591535,1000000000,369057873,101409711,11378,151109154,1715952,4213999,34242104,1000000000,34810411,71477127,209698422,133010846,277099527,33384367,214624209,707475648,5431789,304514681,84512824,507939889,58925471,57863200,284773912,90129665,44857385,69385490,25097815,63710127,397179908,276510789,1000000000,15384817,16255797,1000000000,27582580,34069843,64921549,200224376,273220297,108749308,239978867,444680422,52644676,30371066,80059732,53101984,251234762,289872349,135416926,908016649,2054231,240746328,2198281,22787829,356969036,111068088,37158297,1000000000,126490675,155317865,143102617,373812847,455469375,95937938,374269751,613386171,103596150,68107051,587396306,168265948,192551775,457697701,92277451,48567974,35622258,3686733,1000000000,1000000000,1000000000,2122470,118657642,304523865,8811387,274148263,5731933,1000000000,1000000000,167026068,1000000000,1000000000,101059870,209760597,21053473,311803937,2932696,558382976,14345408,105717892,79475828,4461243,1235990,35870172,370959216,170702344,82652199,277208048,1000000000,228119852,618044000,6905178,127608411,33916773,333859205,29539173,253906302,348051769,178627119,170086840,137896168,13261001,40799196,131158162,31524862,242942594,129118538,1000000000,307379093,156136249,608134557,113890816,96181748,268524479,3996423,379693188,1034540,171823777,1000000000,291988795,17116354,139320296,34493315,1000000000,277666238,217899868,233827009,4611300,243952034,1000000000,54318345,737202617,50768709,69093377,321062402,204227939,613869349,46585187,86803127,363534046,133318008,472898608,199431659,209956689,917538139,69041255,131898687,43034119,316414843,283713501,279143599,503368631,257017112,93799327,37016783,1000000000,4586722,239628127,371819330,1000000000,50504570,51051390,65840502,4401674,50982633,36560195,1000000000,336533284,68023252,35389013,1000000000,44120221,10671039,268030604,541378710,242984243,53905036,21803668,293783286,325573079,303831497,68199734,15458643,450012956,159690254,1000000000,31847383,47224132,78034372,267724204,354633023,374162359,542865454,1000000000,2419624,708040437,347345677,350645576,211638748,27317078,179859845,112287886,75010650,203686790,249693935,3656199,1000000000,816021402,110014048,1000000000,64506254,921122121,137362209,633673144,28707876,304966104,526403595,32919667,194904447,151267091,743705719,1000000000,211350249,636179817,61996526,164586579,1000000000,1000000000,20010751,149515968,23952974,149275811,27937440,314472351,459142271,76401945,5637164,45935166,121765011,209357235,314161878,170202215,184238091,112201888,249240754,1000000000,636388962,29005808,126325314,20519050,397162351,1000000000,35624776,239184681,398470675,1000000000,86793055,149790854,561654498,47102600,1000000000,81257448,161708203,337043479,617415020,524541252,112749575,62313955,64838128,310942389,48778348,7247179,144651017,1000000000,82484654,18325341,294300826,12633292,369106726,241273637,1000000000,525290589,43227693,100605402,543140063,318861476,368824977,6658530,157903426,59283434,26353406,364380493,346176756,170333378,94180844,79838516,1000000000,1000000000,270749635,36498981,26544903,94443762,282331126,36235212,57897263,34261739,1000000000,966920744,84413452,1000000000,24423414,1000000000,91435950,264270549,717971486,600429047,180694024,372741409,1113324,11160280,178007134,7089041,286458652,1000000000,65028529,1000000000,6962087,1000000000,406370108,279938132,82332030,12691251,312165175,1000000000,149816429,517667793,112226273,7034840,18439812,172980807,347883646,8865246,292774410,236002133,171927453,91308635,1569596,61382920,503926814,22259888,1000000000,135351894,68701813,177423567,154579030,317887948,227312418,1000000000,47279042,40566610,46443984,170469011,1000000000,29937693,14215492,273280581,85884365,420600865,69805889,1000000000,82964928,24456578,32647316,141866508,288711797,264998036,151150403,182999644,79766440,289225631,281689433,826780302,459744521,104183512,506136057,691817615,285013610,291073854,586406891,104177534,395324228,770920834,104692072,642619104,80654860,20782210,149059140,27873144,184168910,10848800,174863177,111365078,48363819,137755446,167970493,216937598,259719953,8185982,193851457,1000000000,43506888,120595582,477739365,173167957,73808972,264818787,49747156,136308977,44521601,21160580,51525824,133377043,121173747,66559600,197051776,124566758,51036215,296159778,63895529,607644685,658746680,87981598,179141203,534266367,23990722,12363967,81457364,1000000000,180198125,284491712,439391250,85668559,23002561,85990653,16686950,268077835,38598865,89184222,13249287,4652081,20510504,470291397,163792039,489902202,38684323,94720949,700350576,54764902,371832464,306555410,28325561,823184853,78230694,392172698,329040272,199496322,227563500,446205181,272579126,935051,7658159,341707512,547334212,1000000000,16954409,110390,11457671,298780779,48337673,589670264,127376028,36703380,1000000000,219972500,1000000000,161775968,39041520,405928481,154019199,493620901,1000000000,40298556,384021823,45859393,157986660,155707854,13022629,140170645,52988910,1000000000,231318391,990041328,56713108,34199362,377269831,63500289,87445045,65390496,339284926,609934217,149304816,145350525,130064236,84670969,450824098,1000000000,221944103,122975794,233780683,113769658,789652845,13400985,184215521,33601525,71999825,35516533,207348036,259250178,1000000000,1000000000,529602236,161800751,1000000000,320454481,102058520,16976689,585693094,359882453,292246690,156074463,380939214,1000000000,194980356,1000000000,247839744,2767454,126619702,123734619,189251583,99626388,76990722,731250226,99675055,176878605,73146123,26249181,841141579,274285730,65633535,98801849,119849575,120397227,124410070,16433115,156048149,152164700,20928847,1000000000,106177040,10326059,21666455,8675179,880757104,96323721,208882513,578124041,5897944,16793784,4840042,82286586,1000000000,1000000000,1000000000,193615720,1000000000,1000000000,102221802,61561503,1000000000,39621647,462630237,160026739,667480188,21029723,12930896,76684306,843359476,9185453,533350570,31593395,28518516,1000000000,16669703,554934245,594925074,1000000000,44020628,11902657,295002428,276658186,24491001,68141507,183029650,75627441,1000000000,1000000000,59938147,224616100,39624672,236676565,88577592,1000000000,143205279,1000000000,334176143,3912767,553682822,272003952,275630946,728998544,48153529,130582989,688783501,64813804,687685453,601208906,158738711,193349041,642307615,272375507,13261097,123999991,257790581,227820430,163051111,179445889,23194851,3284767,73224365,15386399,582034422,27070456,210125483,152701906,1000000000,53759258,1000000000,181198225,23209784,839520021,370347898,25638251,91314833,4478527,20537869,1488955,85442769,56049344,1000000000,116677700,512722405,181177705,171758258,244899422,114020313,199351762,124188458,60181310,12761208,48440310,359494469,22197519,300609768,1000000000,9562618,59015843,88963124,113531649,20769220,413459576,90033707,1000000000,42285682,2776814,522052898,683540444,9837714,1000000000,550407089,811784709,96228919,233463026,385352902,1000000000,168613179,215871326,613053,102368022,389761305,234355123,447366844,48451277,665018410,199582162,3788763,106578358,439854345,207123500,1000000000,419269035,772029422,13832276,1000000000,122224238,2633047,5638165,274793011,5577417,629961536,18907933,169941265,80779649,832203083,104632036,894309868,279432477,118234144,128370392,381906349,1000000000,339910580,515135961,59000286,255345736,1000000000,170859318,11224570,1000000000,354697507,312718088,6044595,22954666,45691326,490520857,81466563,1000000000,26917599,1000000000,739960975,252421958,77150421,462244883,597939786,7429784,170690331,4170829,424498689,117436037,98118190,29538300,74930827,170093006,49108753,581916,608764769,381145430,212432175,406791,21561505,421293,28985662,301431288,106778597,175442636,1000000000,69784479,417032601,171072719,31690037,31992884,439900286,158366972,886626937,24031395,186893711,49733460,528098637,270558888,32934690,5250096,132606694,74516006,84431213,118595617,103091357,5250607,15930623,469395762,438451359,123880362,1000000000,1000000000,49408315,923840586,87048649,9465968,129543651,105473657,105461577,83121666,733776507,32016214,714129917,231978023,101777300,576312962,621691289,226499144,408075608,479762739,291959813,176533943,18127801,274880046,124969668,36391110,74445163,136109242,135037077,61187164,149470650,174640686,64706539,1000000000,55150643,39064770,222659118,15510642,561307955,15425044,260467713,323891760,197993612,306174478,75762973,277835481,52933285,310519757,1000000000,586890578,48296681,704873028,13603000,65813964,258286931,588134145,415859626,223098470,1000000000,300514919,141446542,1000000000,60613236,199239699,94129089,140163118,1000000000,521362119,6669545,93385006,117850076,1000000000,216572306,953420525,532901825,25462238,356429653,75622243,86297289,195670790,385342703,257919042,640162787,92257449,103716305,395070299,470509746,591317392,321895500,643936024,278836808,54650009,1000000000,1000000000,263479235,371290829,554360060,208196615,1000000000,29948067,26586238,578039111,598654728,125222854,2762355,360244570,583728387,84742805,1010358,39158181,923991218,220423524,193128112,111748826,246619190,23909602,737035930,257290247,92731174,17911574,3347576,266399978,8089850,531483413,20803866,11822576,1000000000,162588910,76630559,163083644,619156950,137124074,75928213,46770746,223050155,71381932,424467344,652187410,115387736,38595963,121187747,144166485,9130118,26550288,2859783,236159471,331096319,212397925,1000000000,532819621,448923325,28858765,1000000000,127527569,315570091,117062952,297554540,1000000000,1000000000,253653864,14137173,683429731,513965162,1000000000,20631927,255044608,288163692,154859562,427150894,7965594,17521518,489035220,24550650,434185127,117512479,295668408,96207904,5584482,571400667,35458869,78847232,579171296,21373628,232150420,176618122,196187443,80152608,408562558,5122728,1832930,421723974,303581782,470990828,116702127,54509585,94563656,243022990,47672813,115298011,23400239,173552532,254367425,12846909,314830061,585167535,261255475,93769561,222175627,16545922,17675555,35978540,124632152,3763152,6218137,339706475,69477869,134435212,122922110,300054722,1000000000,1000000000,100879559,328777883,1000000000,742721496,67576885,1000000000,1000000000,309560059,87512913,32911882,236835828,90996689,213222356,16062907,525378819,54153562,6143811,16056346,158076586,133252333,81808535,267538299,983939874,293243170,335788430,126899357,40295195,512525633,17147201,22917658,238685830,213111201,127226079,535643204,1000000000,492372184,1000000000,13385915,17289096,335461953,1000000000,106717530,5687223,352358116,12324955,190437435,94582932,29715766,82237937,276759175,332050231,508448850,1000000000,587366773,124402344,1000000000,67862015,10999720,669452669,22863,127560609,275413824,10160401,349061592,101767826,218808001,257388216,393894128,633206517,269012843,761277807,26718670,123579022,395735490,46123542,301135218,24641990,20400655,183271393,27193094,1000000000,74259122,255540738,444443467,72988806,58398604,157667475,346313334,1000000000,89625615,568610364,324469094,219386692,271188523,69396755,28606650,236137837,97091104,139829204,143593767,4324461,22456620,43934645,110024656,5152335,365518927,123511896,1000000000,25779096,44669819,65238947,6816124,85776341,222387439,1000000000,1000000000,59746754,256992368,25428991,328601897,276363365,62570642,155178454,106293832,60047797,164340337,156985828,392174301,20161054,223785082,11714444,218397301,127795042,239596763,3400235,1000000000,37779726,45868576,620767970,46332838,82657195,140981971,112849608,104482870,1358933,994148281,113928720,336235058,1000000000,478159915,437320763,36663380,804591550,150602079,373034656,62542994,1000000000,929145673,742869498,166241299,91948834,1000000000,26032876,14396984,1000000000,1000000000,89161551,115231343,250439212,113959470,233341448,605381511,2571781,48194611,1000000000,18304986,5476094,192897670,1602460,65384949,98498941,529198416,59999557,39285080,944369584,154484684,481279303,724187142,92232992,39389249,268385572,40755788,199543508,503481637,68332583,166969614,220685802,290595340,243999129,1000000000,283908614,1955064,86509480,826859820,235606019,159097735,682757406,838577346,243754849,412370944,195555253,285280375,1000000000,1000000000,638182983,403338259,335961184,87221724,70124079,13233584,45019778,138596181,692245600,45765984,130211295,57102126,401406260,9304641,113463505,835052182,108666649,90253594,371369782,443201191,74184976,185694682,46941230,212277613,1000000000,1000000000,185656486,1000000000,754365335,25333325,11672275,75800575,223108522,592383617,201610892,23429455,380376328,296242204,381297862,287534794,290774855,731150324,832278940,2106406,210700008,1000000000,341531905,1000000000,113919225,41368483,208388582,275445910,347116250,258287267,9062377,1000000000,715395561,89985692,133307360,73411003,1000000000,1000000000,47398746,363067148,338508394,65133689,142217133,94552259,156890310,342264302,138412798,8234342,77846348,250246370,567118488,1000000000,25652362,398153390,279907621,3053400,64687669,2254672,435443182,258496400,276004884,31823297,245485185,98275868,161804015,175897067,7380942,102027031,1000000000,33484223,656759541,166299785,54115608,79953887,107453579,127853755,99816984,691053300,468487694,489511744,123751255,994308351,734884463,602535385,3045612,1000000000,714896597,131177636,13642665,964131083,41602677,2772637,202950853,228480775,154510378,232007820,477637935,98535697,224256764,592427395,163199197,143733377,185322252,263984490,886187760,384144238,446254659,38499917,147649560,102775438,14079444,62254812,1000000000,8184276,72176871,906846896,79828029,18149640,119870481,43856387,95545768,117726502,194378484,18571636,1000000000,105578288,91353496,251898194,247691501,55249558,1000000000,562007116,22889460,390568347,37099331,209687881,13236350,19550525,430893334,393017677,167828585,0,121289725,1000000000,214392462,115080074,122537861,32530066,1000000000,1000000000,379146,181051722,272620664,21769700,133903044,193682949,38752222,158077974,98110503,299405431,50663033,717419598,23494861,145584316,11050623,332210426,739953044,72017451,1000000000,100094797,131903235,1000000000,144261762,1000000000,225401934,46855241,17546335,274349839,179697885,193081473,237436525,33634208,81529526,71247817,428740702,88164379,178388642,225968092,112670201,156709542,1000000000,82617052,226130623,1000000000,1000000000,53418344,56253090,1373576,23682481,95126348,1000000000,16182531,494637678,627957180,1000000000,21136553,145974167,22818349,185441201,67938824,147663270,170906504,106834602,188720119,165279296,549686303,77723421,43708680,750930718,643672442,76308475,191544554,1000000000,31456992,185812229,35737851,30653167,30073721,501897888,40263583,361435202,78720883,393390653,10367713,8180620,445277160,81136993,33576938,518461022,70234071,49762959,94130230,10409893,257653174,521807743,118676121,1000000000,171038764,30646359,33265982,256532367,50381705,92791634,54251006,221904715,906061304,83633550,279023066,50904901,1480900,395259292,128355295,65826661,231965524,513648289,124789906,229196264,318978,637086610,60809169,64297724,40683156,39056932,435125834,1000000000,1000000000,141415365,586686044,8327893,1000000000,794766139,1000000000,92312103,587738,203362487,32359011,920988224,133367455,67418352,63643872,180346430,1101133,127161433,67330901,64939479,4964034,45172598,393642039,101984066,139270209,572857491,37457545,660395825,47444130,115874656,1000000000,250608773,119482668,606644784,81246235,28850270,550894955,246773895,48540567,51425910,63348632,66958996,22164380,233491439,8274869,251989,244314602,19493771,97426110,172591082,391747311,1000000000,2150392,12877585,1000000000,140413752,820524833,60930193,1000000000,199914468,1000000000,61166280,138786943,111686312,124844792,16289932,72376969,45897379,910119133,249576949,81140078,204402183,293804922,121230487,728714695,129557062,349673393,127081568,39718009,7609100,601868597,5334350,1000000000,626742198,830375865,53079776,1000000000,174143877,31428612,392093851,239684174,222630936,246150066,156599737];